AT_arc204_c [ARC204C] Maximize Sum of Mex

给定一个正整数 $N$ 和一个排列 $P = (P_{1}, P_{2}, \dots, P_{N})$，$P$ 是 $1$ 到 $N$ 的一个排列。 有 $Q$ 个询问。每个询问给出非负整数 $A_{0}, A_{1}, A_{2}$，请输出下述问题的答案。保证 $A_{0} + A_{1} + A_{2} = N$。 > 长度为 $N$ 的序列 $B$ 被称为**好序列**，当且仅当它满足以下所有条件： > > - 恰好有 $A_{0}$ 个 $i$ 满足 $1 \leq i \leq N$，使得 $B_{i} = 0$。 > - 恰好有 $A_{1}$ 个 $i$ 满足 $1 \leq i \leq N$，使得 $B_{i} = 1$。 > - 恰好有 $A_{2}$ 个 $i$ 满足 $1 \leq i \leq N$，使得 $B_{i} = 2$。 > > 对于长度为 $N$ 的序列 $B$，其**得分**定义如下： > > - $ \displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}}) $ > > 其中，$\mathrm{MEX}(x, y)$ 表示不等于 $x$ 也不等于 $y$ 的最小非负整数。 > > 请在所有**好序列**中，求得分的最大值。

输入按如下格式从标准输入给出： > $N$ $P_{1}$ $P_{2}$ $\dots$ $P_{N}$ $Q$ $query_{1}$ $query_{2}$ $\cdots$ $query_{Q}$ 其中 $query_{i}$ 表示第 $i$ 个询问，格式如下： > $A_{0}$ $A_{1}$ $A_{2}$

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

### 样例解释 1 对于第一个询问，$B = (0, 1, 2)$ 是一个好序列。该序列的得分为 $\mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3$，即 $3$。不存在得分更高的好序列，因此第一行输出 $3$。 ### 数据范围 - $1\leq N\leq 3\times 10^{5}$ - $(P_{1}, P_{2}, \dots, P_{N})$ 是 $1$ 到 $N$ 的一个排列。 - $1\leq Q\leq 3\times 10^{5}$ - $0\leq A_{i}$ - 对每个询问，$A_{0} + A_{1} + A_{2} = N$。 - 所有输入值均为整数。 由 ChatGPT 4.1 翻译