PokéTrainer Little Joseph is very good in Biology and wants to clone Mew. Suddenly, something has happened! An evil super-Mankey randomly appeared in front of him and passed him the DNA of Mew. Excited at the new opportunity, Little Joseph began studying Mew's DNA in his secret lab (and can only be accessed if you have all 9 pieces of the Secret Laboratory Map).
Little Joseph found out that Pokémon DNA is not made of A, C, T and G but rather made out of a sequence of integers. He also found out that Mew's DNA are made out of "coding integers" and "non-coding integers", which means that only certain integers in the DNA sequence are used by the body.
The rest of the non-coding regions will actually form miRNA which is a dsRNA which will be brought by Dicer to the RNA-Induced Silencing Complex for controlling gene expression. But you don't need to know that.
Little Joseph found out that there is a coding sequence that is a subsequence of the DNA sequence. However, it need not be continuous in the DNA sequence, meaning that a DNA sequence of 1 7 2 5 can have a coding sequence of 1 7 5 (even though this sequence is not continuous in the DNA).
Little Joseph also found out that the coding sequence is always of odd length N, with the first (N+1)/2 integers of the sequence making a strictly increasing sequence and the last (N+1)/2 integers of the sequence making a strictly decreasing sequence.
For example, 1 2 3 4 3 2 0 is a coding sequence but both 1 2 3 4 3 2 2 and 1 2 3 4 5 3 1 is not.
These conditions will allow for many coding sequence, but the coding sequence that Little Joseph needs is always the longest possible coding sequence.
Your task as a PokéProgrammer is to find the length of the longest coding sequence.
Input
The first line of input contains an integer
N (1 ≤
N ≤ 15,000) representing the number of integers in Mew's DNA sequence. The next line contains
N integers representing Mew's DNA sequence.
Output
Print out the length of the longest coding sequence on a single line.
Sample Input 1
11
1 2 3 4 5 1 4 3 2 1 10
Sample Output 1
9
Explanation for Sample Output 1
This is gotten from the coding sequence of 1 2 3 4 5 4 3 2 1.