分数: 900 点
问题陈述
给你一个正整数 N 和排列 P = (P_{1}, P_{2}, \dots, P_{N}) of (1, 2, \dots , N).
流程 Q 查询。在每个查询中,非负整数 给出了 A_{0}, A_{1}, A_{2} ,因此输出以下问题的答案。可以保证 A_{0} + A_{1} + A_{2} = N.
一个序列 B 长度 N 被称为 好的序列 当且仅当满足以下所有条件时:
- 正好有 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.
对于序列 B 长度 N, 分数 游戏的 定义如下:
- \displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})
在这里, \mathrm{MEX}(x, y) 被定义为既不是的最小非负整数 x 也不 y.
找到最大值 分数 游戏的 总的来说 好的序列.
约束
- 1\leq N\leq 3\times 10^{5}
- (P_{1}, P_{2}, \dots , P_{N}) 是一个排列 (1, 2, \dots , N).
- 1\leq Q\leq 3\times 10^{5}
- 0\leq A_{i}
- 对于每个查询, A_{0} + A_{1} + A_{2} = N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
3 2 3 1 2 1 1 1 1 0 2
示例输出 1
3 2
对于第一个查询, B = (0, 1, 2) 是一个很好的序列。该序列的得分为 \mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3,即 3。不存在分数大于的好序列 3,所以输出 3 在第一行。
示例输入 2
7 6 3 4 5 2 1 7 4 2 2 3 4 1 2 0 3 4 1 2 4
示例输出 2
8 9 0 4
示例输入 3
9 1 6 7 3 5 8 9 2 4 10 5 3 1 0 7 2 0 6 3 1 3 5 4 0 5 4 2 3 1 5 3 4 5 0 2 2 5 2 5 2
示例输出 3
14 0 0 4 7 11 4 13 8 8