Wavio is a sequence of integers. It has some interesting properties. • Wavioisofoddlengthi.e. L=2∗n+1. • The first (n + 1) integers of Wavio sequence makes a strictly increasing sequence. • The last (n + 1) integers of Wavio sequence makes a strictly decreasing sequence. • No two adjacent integers are same in a Wavio sequence. Forexample1,2,3,4,5,4,3,2,0isanWaviosequenceoflength9. But1,2,3,4,5,4,3,2,2is not a valid wavio sequence. In this problem, you will be given a sequence of integers. You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence. Consider, the given sequence as : 1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1. HerethelongestWaviosequenceis: 123454321. So,theoutputwillbe‘9’. Input The input file contains less than 75 test cases. The description of each test case is given below. Input is terminated by end of file. Each set starts with a postive integer, N (1 ≤ N ≤ 10000). In next few lines there will be N integers. Output For each set of input print the length of longest wavio sequence in a line. Sample Input 10 1 2 3 4 5 4 3 2 1 10 19 1232123432154123221 5 12345 Sample Output 9 9 1