单峰序列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

明明最近遇到一个数学问题:给定n个数字(A1,A2,A3......An),每个数字均是小于2^31的正整数,现需要知道这n个数字中的最长单峰子序列长度是多少。所谓单峰序列是指满足如下条件之一的子序列:
(1)Ak1<Ak2<Ak3<......<Akm (k1,k2,k3....km均在1到n之间)
(2)Ak1>Ak2>Ak3>......>Akm (k1,k2,k3....km均在1到n之间)
(3)Ak1<Ak2<Ak3<...<Amid-1<Amid>Amid+1>...>Akm-2>Akm-1>Akm (k1,k2,k3....km均在1到n之间)
现在明明很忙,他想请你帮他解决这个问题,而解决这个问题的好处是他可以让你此时此刻多获得一个彩色气球。你能帮他吗?

Input

输入包含多组数据,每组数据的格式如下:
一个正整数n(1<=n<=1000),表示有多少个数字。
紧跟一行有n个正整数A1,A2....An。(0<=Ai<=2^31)

Output

对于每组输入,输出一个正整数ans,表示该组数据中最长单峰子序列的长度是多少。每个输出占一行。

Sample Input

2
1 2
3
1 3 2
4
1 5 4 6

Sample Output

2
3
3

Hint

Source