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.