最长上凸序列

Time Limit: 5000 ms

Memory Limit: 65535 ms

Description

相信大家都做过了最长递增子序列问题,
现在有一个新问题,找一个先递增后递减的最长序列,就叫做最长上凸序列。

Input

多case 对于每个case 第一行一个整数n(4< n < 100000) 第二行n个整数

Output

对于每组case输出最长上凸序列的长度

Sample Input

10
1 2 3 4 5 6 7 8 9 0
6
2 5 8 3 6 3

Sample Output

10
5

Hint

Source

treert

提交代码