题目描述

$FTY$有一个序列$a$,他定义一个序列的价值为其满足“优美”性质的子序列的最长长度。

一个序列$b$是优美的,当且仅当其满足$b_1<b_2 , b_2>b_3 , b_3<b_4, b_4>b_5 \dots$或$b_1>b_2 , b_2<b_3 , b_3>b_4, b_4<b_5 \dots$。

现在FTY想要知道序列$a$的价值是多少。


输入格式

输入第一行一个整数$n(n \leq 2000)$,表示序列$a$的长度。

接下来一行共$n$个整数,其中第$i$个整数为$a_i(1\leq a_i \leq n)$。


输出格式

输出一行一个整数表示序列$a$的价值。


样例数据

输入

样例一
5
1 2 1 2 1

样例二
8
1 4 5 2 2 1 5 3

样例三
10
1 9 2 3 10 6 3 7 4 1

输出

样例一
5

样例二
5

样例三
7

备注


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务