Badge Pairs in a Row

Time limit: 2000 msMemory limit: 256 MB

A festival has a row of $N$ souvenir booths. The booth at position $i$ sells a badge of type $T_i$ .

A non-empty contiguous segment from booth $L$ to booth $R$ is called paired if no badge type appears exactly once inside it. More formally, for each integer type $x$ , let $C_x(L,R)$ be the number of indices $i$ such that $L \le i \le R$ and $T_i = x$ . The segment is paired if, for every type $x$ , either $C_x(L,R) = 0$ or $C_x(L,R) \ge 2$ .

Find the maximum possible length of a paired segment. If there is no paired segment, the answer is $0$ .

Input

The input has exactly $2$ lines.

Line $1$ contains one integer $N$ ( $1 \le N \le 200000$ ), the number of booths.

Line $2$ contains exactly integers (), where is the badge type at booth .

Output

Output exactly $1$ line.

The line contains one integer $M$ : the maximum value of $R-L+1$ over all paired segments. If no non-empty paired segment exists, output $0$ . The line must contain no other tokens.

Samples

Sample 1

Input

5
1 2 1 3 3

Output

The segment from booth $4$ to booth $5$ has two badges of type $3$ . No paired segment has length greater than $2$ .

Sample 2

Input

6
7 4 7 4 9 9

Output

In the whole line, each occurring type appears exactly $2$ times, so all $6$ booths can be chosen.

Badge Pairs in a Row

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions

Sample 3