在 APIO 的奇妙领域里，住着一位年轻而聪慧的学生名叫 Alice。Alice 对解决挑战她数学能力的难题有着无穷的好奇心。有一天，她偶然发现了一个长度为 $N$ 的神秘数字序列（即 $A[0], A[1], \dots, A[N-1]$），她无法抗拒探索其秘密的诱惑。

在这里，她想与你分享她的一些发现。但在那之前，为了方便起见，我们需要定义一些概念：

• 定义 $W(l, r, x)$ 为 $\sum_{i=l}^{r} \mathbb{I}[A[i] = x]$，即 $x$ 在 $A[l] \dots A[r]$ 中出现的次数。
• 定义非空整数序列 $B[0], B[1], \dots, B[k-1]$ 的中位数集合为 $S(\{B[0], B[1], \dots, B[k-1]\})$。Alice 将在下面向你展示如何逐步计算中位数集合：
  • 首先，将元素 $B[0], B[1], \dots, B[k-1]$ 按升序排序，得到序列 $C[0], C[1], \dots, C[k-1]$。
  • 然后，$S(\{B[0], B[1], \dots, B[k-1]\}) = \{C[\lfloor \frac{k-1}{2} \rfloor], C[\lceil \frac{k-1}{2} \rceil]\}$。
• 为了加深你对 $S$ 计算的理解，让我们考虑几个例子：
  • $S(\{6, 3, 5, 4, 6, 2, 3\}) = \{4\}$。
  • $S(\{4, 2, 3, 1\}) = \{2, 3\}$。
  • $S(\{5, 4, 2, 4\}) = \{4\}$。

Alice 渴望找到 $\max_{x \in S(l, r)} W(l, r, x)$ 的最大值，其中 $0 \le l \le r \le N-1$，因为这是一个具有挑战性的任务。项 $S(l, r)$ 表示从 $A[l] \dots A[r]$ 导出的中位数集合（如前所述，即 $S(A[l], \dots, A[r])$）。尽管 Alice 已经得到了答案，但她寻求协助来验证它，并恳请你帮助编写计算程序。

实现细节

你应该实现以下过程：

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

• $N$：序列 $A$ 的长度。
• $A$：长度为 $N$ 的数组，描述序列 $A$。
• 此过程应返回一个整数，表示所有可能的对 $(l, r)$ 中的最大值。
• 此过程将被调用恰好一次。

样例

样例 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)$ 在所有可能的对中具有最大值。

样例 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$ 满足 $\forall 0 \le i < x, A[i] \le A[i+1]$ 且 $\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$）。
6. (22 分)：$N \le 8 \times 10^4$。
7. (18 分)：无附加限制。

说明

示例评测程序按以下格式读取输入：

第 1 行：$N$ 第 2 行：$A[0] \ A[1] \ \dots \ A[N-1]$

示例评测程序按以下格式打印你的输出：

第 1 行：sequence 的返回值。