问题描述

T先生以“诸行无常”为座右铭，挑战各种事物。T先生长期参加了某个比赛，该比赛具有评级功能，每次参加后评级会发生变动。这些变动被总结在图表中。

现在，T先生正在观察他的评级变动所绘制的图表。他突然想要去除图表中的一些点，并将它们连接起来，形成一条总是上下波动的折线图，他称之为“常ならず图”。此外，他对图表中包含的点的数量最感兴趣。

现在，你要为T先生计算，从他的评级变动所绘制的图表中，可以得到的“常ならず图”中最多的点的数量。

给定T先生参加某个比赛后的评级$N$个，按时间顺序给出。当你从中删除一些点并创建“常ならず图”时，请计算可能的最大点数。如果不能创建“常ならず图”，请输出0。

一个图表 $X=\\{x_1,x_2,x_3,..x_n\\}$ 被称为“常ならず图”，当且仅当 $|X|$ 大于等于3且满足 $x_1＜x_2＞x_3＜x_4＞...$ 或者 $x_1＞x_2＜x_3＞x_4<...$。换句话说，如果包含的顶点数小于3，则不是“常ならず图”。

输入

输入以以下格式从标准输入中给出。

$N$ $R_1$ $R_2$ … $R_N$

• 第1行是一个整数 $N (1 ≦ N ≦ 3000)$，表示T先生参加比赛的次数。
• 第2行是T先生参加第 i (1 ≦ i ≦ N) 次比赛后的评级 $R_i (-10^5 ≦ R_i ≦ 10^5)$，空格分隔。

输出

当你从给定的图表中删除一些点并创建“常ならず图”时，请计算可能的最大点数，并在一行中输出。请不要忘记结尾换行符。

示例1

4
1 2 5 1

输出示例1

3

示例2

5
1 2 3 4 5

输出示例2

0