Hamza wants to add a new concept to the arrays world. The new concept is called "The good segment", which is the segment where its first element is equal to the last one.
Practically, for any array with size $n$, the segment $a_l , a_{l+1} , a_{l+2} , … , a_{r}$ is called good segment if $a_l = a_r$.
Hamza wants to experience your understanding of this concept by giving you an array with size $n$ and asking you to find the longest $k$-good segment.
The first line of input contains an integer $n$ $(1 \le n \le 10^6)$, denoting the size of the array.
The second line contains $n$ space-separated integers $a_1,a_2,...,a_n$ $(-5·10^5 \le a_i \le 5·10^5)$, representing the elements of the array.
Output a single integer $k$, the length of the longest good segment.
Input | Output |
---|---|
7 1 3 6 9 1 3 2 Copy
|
5 Copy
|