수열

APIO의 세계에 Alice라는 똑똑하고 호기심 많은 학생이 살았다. 그녀는 길이가 $N$인 수열 $A\[0]$, $A\[1]$, $\cdots$, $A\[N - 1]$을 발견했다. 그녀가 알아낸 내용 일부를 여러분과 나누려고 한다. 먼저 몇 가지를 정의한다.

• $W(l, r,x)$를 $\displaystyle\sum\_{i=l}^{r}{\mathrm{I}\[A\[i] = x]}$로 정의한다. 이는 $A\[l] \cdots A\[r]$에서 $x$가 나타나는 횟수이다.
• 비어 있지 않은 정수 수열 $B\[0]$ $B\[1]$ $\cdots$ $B\[k - 1]$의 중앙값 집합 $S(\\{B\[0], B\[1], \cdots ,B\[k - 1]\\})$은 다음 두 단계로 구한다.
  • 먼저 $B\[0], B\[1], \cdots ,B\[k - 1]$을 오름차순으로 정렬해 $C\[0], C\[1], \cdots ,C\[k - 1]$을 얻는다.
  • 그다음 $S = \\{C\[\lfloor \frac{k-1}{2} \rfloor ], C\[\lceil \frac{k-1}{2} \rceil ] \\}$이다.
  • 예를 들어 $S(\\{6, 3, 5, 4, 6, 2, 3\\}) = \\{4\\}$, $S(\\{4, 2, 3, 1\\}) = \\{2, 3\\}$, $S(\\{5, 4, 2, 4\\}) = \\{4\\}$이다.

Alice는 모든 $0 \le l \le r \le N - 1$에 대해 $\displaystyle\max\_{x \in S(l,r)}{W(l, r,x)}$의 최댓값을 구하고자 한다. 여기서 $S(l,r)$은 $S(A\[l], \cdots ,A\[r])$이다. Alice는 이미 답을 구했고, 이를 검증할 프로그램을 작성해 달라고 요청한다.

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