Sequence

In the realm of APIO, a young and brilliant student named Alice found a sequence of length $N$: $A\[0]$, $A\[1]$, $\cdots$, $A\[N - 1]$. She wants to share some of her discoveries with you. First, here are some definitions.

• Define $W(l, r,x)$ as $\displaystyle\sum\_{i=l}^{r}{\mathrm{I}\[A\[i] = x]}$, the number of occurrences of $x$ in $A\[l] \cdots A\[r]$.
• Define the set of medians of a non-empty integer sequence $B\[0]$ $B\[1]$ $\cdots$ $B\[k - 1]$ as $S(\\{B\[0], B\[1], \cdots ,B\[k - 1]\\})$. Alice computes it in two steps.
  • First, sort $B\[0], B\[1], \cdots ,B\[k - 1]$ in ascending order to get $C\[0], C\[1], \cdots ,C\[k - 1]$.
  • Then $S = \\{C\[\lfloor \frac{k-1}{2} \rfloor ], C\[\lceil \frac{k-1}{2} \rceil ] \\}$.
  • For example, $S(\\{6, 3, 5, 4, 6, 2, 3\\}) = \\{4\\}$, $S(\\{4, 2, 3, 1\\}) = \\{2, 3\\}$, and $S(\\{5, 4, 2, 4\\}) = \\{4\\}$.

Alice wants the maximum of $\displaystyle\max\_{x \in S(l,r)}{W(l, r,x)}$ over all $0 \le l \le r \le N - 1$, where $S(l,r)$ is $S(A\[l], \cdots ,A\[r])$. She already has the answer and wants you to write a program that verifies it.

• $1 \le N \le 5 \times 10^5$
• $1 \le A\[i] \le N$