Longest Palindrome

Professor BP loves palindromes. He wrote a sequence $V$ of $N$ positive integers on the blackboard and was delighted to see that it contained long palindromic substrings.

However, during the break, one of his students erased some of the numbers from the sequence. Now, Professor BP wants to restore the sequence by replacing all the erased numbers with the same number $x$ of his choice.

Your task is to determine the length of the longest palindromic contiguous substring that can be obtained after choosing an optimal value for $x$.

Input data

The input file consists of two lines:

• a line containing integer $N$.
• a line containing the $N$ integers $V_{0}, \, \ldots, \, V_{N-1}$. If the number at position $i$ is erased, $V_i = -1$, otherwise $V_i$ is a number between $1$ and $N$.

Output data

Print a single integer: the length of the longest contiguous palindromic substring that can be obtained after replacing all erased numbers with the same number $x$ of Professor BP's choice.

Constraints and clarifications

• $1 \le N \le 200 \ 000$.
• $-1 \le V_i \le N$ and $V_i \neq 0$ for each $i=0\ldots N-1$.

DISCLAIMER! Some tests have been improved compared to the competition tests.

Example

stdin

10
6 5 5 -1 2 -1 4 5 -1 -1

stdout

5

Explanation

If Professor BP replaces all the erased numbers with the number $4$, he obtains the sequence $6 \ 5 \ 5 \ 4 \ 2 \ 4 \ 4 \ 5 \ 4 \ 4$.

The last $5$ numbers form a palindromic sequence $\texttt{4 4 5 4 4}$ and it is the longest he can achieve.