C - Maximize Sum of Mex Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

正整数 N と (1, 2, \dots , N) の順列 P = (P_{1}, P_{2}, \dots, P_{N})が与えられます。

Q 個のクエリを処理してください。各クエリでは非負整数 A_{0}, A_{1}, A_{2} が与えられるので以下の問題の答えを出力してください。なお、A_{0} + A_{1} + A_{2} = N であることが保証されます。

長さ N の数列 B であって、以下の条件をすべて満たす数列を good な数列とします。

  • B_{i} = 0 が成り立つ 1 以上 N 以下の整数 i はちょうど A_{0} 個
  • B_{i} = 1 が成り立つ 1 以上 N 以下の整数 i はちょうど A_{1} 個
  • B_{i} = 2 が成り立つ 1 以上 N 以下の整数 i はちょうど A_{2} 個

長さ N の数列 B に対して、スコアを以下のように定義します。

  • \displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})

ただし、\mathrm{MEX}(x, y) は x でも y でもない最小の非負整数であると定義します。

good な数列全てに対するスコアの最大値を求めてください。

制約

  • 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

1 番目のクエリについて、B = (0, 1, 2) は good な数列です。この数列のスコアは \mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3 より 3 です。3 よりスコアが大きい good な数列は存在しないので、1 行目には 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

Score : 900 points

Problem Statement

You are given a positive integer N and a permutation P = (P_{1}, P_{2}, \dots, P_{N}) of (1, 2, \dots , N).

Process Q queries. In each query, non-negative integers A_{0}, A_{1}, A_{2} are given, so output the answer to the following problem. It is guaranteed that A_{0} + A_{1} + A_{2} = N.

A sequence B of length N is called a good sequence if and only if it satisfies all of the following conditions:

  • There are exactly A_{0} integers i with 1 \leq i \leq N such that B_{i} = 0.
  • There are exactly A_{1} integers i with 1 \leq i \leq N such that B_{i} = 1.
  • There are exactly A_{2} integers i with 1 \leq i \leq N such that B_{i} = 2.

For a sequence B of length N, the score is defined as follows:

  • \displaystyle\sum_{i = 1}^{N}\mathrm{MEX}(B_{i}, B_{P_{i}})

Here, \mathrm{MEX}(x, y) is defined as the minimum non-negative integer that is neither x nor y.

Find the maximum value of the score over all good sequences.

Constraints

  • 1\leq N\leq 3\times 10^{5}
  • (P_{1}, P_{2}, \dots , P_{N}) is a permutation of (1, 2, \dots , N).
  • 1\leq Q\leq 3\times 10^{5}
  • 0\leq A_{i}
  • For each query, A_{0} + A_{1} + A_{2} = N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
P_{1} P_{2} \dots P_{N}
Q
query_{1}
query_{2}
\cdots
query_{Q}

Here query_{i} is the i-th query, given in the following format:

A_{0} A_{1} A_{2}

Output

Output Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

3
2 3 1
2
1 1 1
1 0 2

Sample Output 1

3
2

For the first query, B = (0, 1, 2) is a good sequence. The score of this sequence is \mathrm{MEX}(0, 1) + \mathrm{MEX}(1, 2) + \mathrm{MEX}(2, 0) = 2 + 0 + 1 = 3, which is 3. There is no good sequence with a score greater than 3, so output 3 on the first line.

Sample Input 2

7
6 3 4 5 2 1 7
4
2 2 3
4 1 2
0 3 4
1 2 4

Sample Output 2

8
9
0
4

Sample Input 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

Sample Output 3

14
0
0
4
7
11
4
13
8
8