{"raw_statement":[{"iden":"background","content":"**由于部分 BUG，使用 C++14 (GCC9) 提交会产生编译错误，请使用 C++14 等语言进行提交。**\n\n提交时，无需引用 `sequence.h`。你提交的代码中需要实现以下函数：\n\n```cpp\nint sequence(int N, std::vector A)\n```"},{"iden":"statement","content":"在迷人的 APIO 国，居住一位着年轻智慧的学生 Alice。Alice 对解决能挑战她数学能力的有趣问题有着永不满足的好奇心。一天，她在解决一个神秘的有关长为 $N$ 的序列 (即 $A[0], A[1], \\cdots, A[N-1]$ ) 的问题时遇到了困难，她无法抗拒探索答案的诱惑力。\n\n现在，她想要与你分享一些她的发现。不过，为了更好的理解，我们需要给出以下定义:\n\n- 定义 $W(l, r, x)$ 为 $\\sum_{i=l}^{r} \\mathbb{I}[A[i]=x]$, 即 $x$ 在 $A[l] \\cdots A[r]$ 中的出现次数。\n- 定义一个非空整数序列 $B[0] B[1] \\cdots B[k-1]$ 的中位数集合为 $S(\\{B[0], B[1] \\cdots B[k-1]\\})$, 然后 Alice 会展示如何分步计算中位数集合:\n\n○首先，将序列 $B[0], B[1], \\ldots, B[k-1]$ 按照升序排序，令排好序的序列为 $C[0], C[1], \\ldots, C[k-1]_{0}$\n\n○ 然后, $S(\\{B[0], B[1] \\cdots B[k-1]\\})=\\left\\{C\\left[\\left\\lfloor\\frac{k-1}{2}\\right]\\right], C\\left[\\left\\lceil\\frac{k-1}{2}\\right\\rceil\\right]\\right\\}$ 。\n\n○ 为了能更好的理解 $S$ 的计算，以下为一些例子:\n\n- $S(\\{6,3,5,4,6,2,3\\})=\\{4\\}$.\n- $S(\\{4,2,3,1\\})=\\{2,3\\}$\n- $S(\\{5,4,2,4\\})=\\{4\\}$.\n\n作为一道具有挑战性的问题, Alice 想对于所有的 $(l, r)(0 \\leq l \\leq r \\leq N-1)$ 找到其价值 $\\max _{x \\in S(l, r)} W(l, r, x)$ 的最大值。其中 $S(l, r)$ 代表 $A[l] \\cdots A[r]$ 导出的中位数集合（正如之前提到的 $S(A[l], \\cdots, A[r])$ )。虽然 Alice 已经得到了答案，她需要核对答案的正确性，所以她找到了你，希望你能编程解决问题。\n\n### 实现细节\n\n你需要实现如下的过程:\n\n```cpp\nint sequence(int N, std:: vector A);\n```\n- $N$ ：序列 $A$ 的长度。\n- $A$ : 一个长度为 $N$ 的数组，即输入中提到的序列 $A$ 。\n- 该函数应返回一个整数，代表所有可行 $(l, r)$ 价值的最大值。\n- 这个函数恰好被调用一次。\n"},{"iden":"input","content":"评测程序示例读取如下格式的输入:\n\n第 $1$ 行: $N$\n\n第 $2$ 行: $A[0] A[1] \\cdots A[N-1]$"},{"iden":"output","content":"评测程序示例按照如下的格式打印你的答案:\n\n第 $1$ 行：`sequence` 的返回值。"},{"iden":"note","content":"### 例子\n\n#### 样例 1\n\n考虑如下的调用:\n\n```cpp\nsequence(7,{1,2,3,1,2,1,3});\n```\n\n函数应返回 $3$。\n\n在这个样例中, $S(0,5)=\\{1,2\\}, W(0,5,1)=3 ， W(0,5,2)=2$ ，所以 $(0,5)$ 的价值为 3 。\n\n容易验证 $(0,5)$ 在所有合法的 $(l, r)$ 二元组中有着最大的价值。\n\n#### 样例 2\n\n考虑如下的调用:\n\n```cpp\nsequence(9,{1,1,2,3,4,3,2,1,1});\n```\n\n函数应返回 $2$。\n\n### 样例 3\n\n考虑如下的调用:\n\n```cpp\nsequence(14,{2,6,2,5,3,4,2,1,4,3,5,6,3,2});\n```\n\n函数应返回 $3$。\n\n### 约束条件\n\n- $1 \\leq N \\leq 5 \\times 10^{5}$\n- $1 \\leq A[i] \\leq N$\n\n### 子任务\n\n1. (11 分)：$N \\leq 100$ 。\n2. (17 分)：$N \\le 2 \\times 10^{3}$ 。\n3. (7 分)：存在一个 $x$ 满足 $\\forall 0 \\leq i