在迷人的 APIO 国，居住一位着年轻智慧的学生 Alice。Alice 对解决能挑战她数学能力的有趣问题有着永不满足的好奇心。一天，她在解决一个神秘的有关长为 $N$ 的序列 (即 $A[0],A[1],\cdots ,A[N-1]$ ) 的问题时遇到了困难，她无法抗拒探索答案的诱惑力。

现在，她想要与你分享一些她的发现。不过，为了更好的理解，我们需要给出以下定义:

• 定义 $W(l,r,x)$ 为 $\sum _{i=l}^r\mathbb{I}[A[i]=x]$, 即 $x$ 在 $A[l]\cdots A[r]$ 中的出现次数。
• 定义一个非空整数序列 $B[0]B[1]\cdots B[k-1]$ 的中位数集合为 $S(\{B[0],B[1]\cdots B[k-1]\})$, 然后 Alice 会展示如何分步计算中位数集合:

首先，将序列 $B[0],B[1],\dots ,B[k-1]$ 按照升序排序，令排好序的序列为 $C[0],C[1],\dots ,C[k-1{]}_0$

然后, $S(\{B[0],B[1]\cdots B[k-1]\})=\{C\left[\lfloor \frac{k-1}{2}]\right],C\left[\lceil \frac{k-1}{2}\rceil \right]\}$ 。

为了能更好的理解 $S$ 的计算，以下为一些例子:

• $S(\{6,3,5,4,6,2,3\})=\{4\}$.
• $S(\{4,2,3,1\})=\{2,3\}$
• $S(\{5,4,2,4\})=\{4\}$.

作为一道具有挑战性的问题, Alice 想对于所有的 $(l,r)(0\le l\le r\le N-1)$ 找到其价值 $\underset{x\in S(l,r)}{max}W(l,r,x)$ 的最大值。其中 $S(l,r)$ 代表 $A[l]\cdots A[r]$ 导出的中位数集合（正如之前提到的 $S(A[l],\cdots ,A[r])$ )。虽然 Alice 已经得到了答案，她需要核对答案的正确性，所以她找到了你，希望你能编程解决问题。

实现细节

你需要实现如下的过程:

int sequence(int N, std:: vector<int> A);

• $N$ ：序列 $A$ 的长度。
• $A$ : 一个长度为 $N$ 的数组，即输入中提到的序列 $A$ 。
• 该函数应返回一个整数，代表所有可行 $(l,r)$ 价值的最大值。
• 这个函数恰好被调用一次。

评测程序示例读取如下格式的输入:

第 $1$ 行: $N$

第 $2$ 行: $A[0]A[1]\cdots A[N-1]$

评测程序示例按照如下的格式打印你的答案:

第 $1$ 行：sequence 的返回值。

样例 1

input

7
1 2 3 1 2 1 3

output

3

样例 2

input

9
1 1 2 3 4 3 2 1 1

output

2

样例 3

input

14
2 6 2 5 3 4 2 1 4 3 5 6 3 2

output

3

提示

例子

样例 1

考虑如下的调用:

sequence(7,{1,2,3,1,2,1,3});

函数应返回 $3$。

在这个样例中, $S(0,5)=\{1,2\},W(0,5,1)=3，W(0,5,2)=2$ ，所以 $(0,5)$ 的价值为 3 。

容易验证 $(0,5)$ 在所有合法的 $(l,r)$ 二元组中有着最大的价值。

样例 2

考虑如下的调用:

sequence(9,{1,1,2,3,4,3,2,1,1});

函数应返回 $2$。

样例 3

考虑如下的调用:

sequence(14,{2,6,2,5,3,4,2,1,4,3,5,6,3,2});

函数应返回 $3$。

约束条件

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

子任务

1. (11 分)：$N\le 100$ 。
2. (17 分)：$N\le 2\times {10}^3$ 。
3. (7 分)：存在一个 $x$ 满足 $\mathrm{\forall }0\le i<x,A[i]\le A[i+1]$ 且 $\mathrm{\forall }x<i<N,A[i]\le A[i-1]$ 。
4. (12 分)：$A[i]\le 3$ 。
5. (13 分)：$W(0,N-1,A[i])\le 2$ (对于所有满足 $0\le i\le N-1$ 的 $i$ )。
6. (22 分)：$N\le 8\times {10}^4$ 。
7. (18 分)：没有额外限制。