The segment is not even.

Two sequences $s$ and $t$ of equal length are even if they can be made equal to each other by repeating the following operation as many times as you want.

• Choose two positive integers $i$ and $j$ with $1 \leq i < j \leq |s|$, and swap the values of $s_i$ and $s_j$.

Given a sequence $A$ of length $N$, let $A[l,r]=[A_{l},A_{l+1},\dots,A_{r}]$ be the contiguous subsequence containing only the elements from the $l$-th to the $r$-th element of $A$. Find the maximum length of $A[l,r]$ that satisfies the following condition.

Let $m=\left\lfloor\frac{l+r}{2}\right\rfloor$. Then $A[l,m]$ and $A[m+1,r]$ are even to each other.

The first line contains an integer $N$, the length of sequence $A$. ($1 \leq N \leq 5\,000$)

The second line contains $N$ integers $A_{1},A_{2},\dots,A_{N}$, separated by spaces. ($1 \leq A_i \leq 10^{9}$)

Print the maximum length of $A[l,r]$ when splitting the contiguous subsequence $A[l,r]$ in half gives two sequences that are even to each other.

If no such contiguous subsequence exists, print $0$.