题目描述

在 LibreOJ，本题仅保证使用 GNU C++17 编译将得到预期的编译结果，使用其他编译器版本不保证编译结果一定符合预期。

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

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

• 定义 $W(l,r,x)$ 为 $\sum_{i=l}^r \mathbb{I}[A[i]=x]$，即 $x$ 在 $A[l]\ldots A[r]$ 中的出现次数。
• 定义一个非空整数序列 $B[0], B[1],\ldots, B[k - 1]$ 的中位数集合为 $S(\{B[0],B[1],\ldots ,B[k - 1]\})$，然后 Alice 会展示如何分步计算中位数集合：
  • 首先，将序列 $B[0],B[1],\ldots ,B[k-1]$ 按照升序排序，令排好序的序列为 $C[0],C[1],\ldots ,C[k - 1]$。
  • 然后，$S(\{B[0],B[1],\ldots , 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 想对于所有的 $(l,r)\ (0\le l\le r\le N-1)$ 找到其价值 $\max_{x\in S(l,r)}W(l,r,x)$ 的最大值。其中 $S(l,r)$ 代表 $A[l]\ldots A[r]$ 导出的中位数集合（正如之前提到的 $S(A[l],\ldots,A[r])$）。虽然 Alice 已经得到了答案，她需要核对答案的正确性，所以她找到了你，希望你能编程解决问题。

实现细节

请在程序开头引入库 sequence.h。

#include "sequence.h"

你需要实现如下的过程：

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

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

7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2

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$ 的 $i$）
6. （$22$ 分）：$N \le 8 \times 10^4$
7. （$18$ 分）：没有额外限制

评测程序示例

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

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

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

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