{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $N$ and a permutation $P = (P_{1}, P_{2}, \\dots, P_{N})$ of $(1, 2, \\dots , N)$.\nProcess $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$.\n\n> A sequence $B$ of length $N$ is called a **good sequence** if and only if it satisfies all of the following conditions:\n> \n> *   There are exactly $A_{0}$ integers $i$ with $1 \\leq i \\leq N$ such that $B_{i} = 0$.\n> *   There are exactly $A_{1}$ integers $i$ with $1 \\leq i \\leq N$ such that $B_{i} = 1$.\n> *   There are exactly $A_{2}$ integers $i$ with $1 \\leq i \\leq N$ such that $B_{i} = 2$.\n> \n> For a sequence $B$ of length $N$, the **score** is defined as follows:\n> \n> *   $\\displaystyle\\sum_{i = 1}^{N}\\mathrm{MEX}(B_{i}, B_{P_{i}})$\n> \n> Here, $\\mathrm{MEX}(x, y)$ is defined as the minimum non-negative integer that is neither $x$ nor $y$.\n> Find the maximum value of the **score** over all **good sequences**."},{"iden":"constraints","content":"*   $1\\leq N\\leq 3\\times 10^{5}$\n*   $(P_{1}, P_{2}, \\dots , P_{N})$ is a permutation of $(1, 2, \\dots , N)$.\n*   $1\\leq Q\\leq 3\\times 10^{5}$\n*   $0\\leq A_{i}$\n*   For each query, $A_{0} + A_{1} + A_{2} = N$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$P_{1}$ $P_{2}$ $\\dots$ $P_{N}$\n$Q$\n$query_{1}$\n$query_{2}$\n$\\cdots$\n$query_{Q}$\n\nHere $query_{i}$ is the $i$\\-th query, given in the following format:\n\n$A_{0}$ $A_{1}$ $A_{2}$"},{"iden":"sample input 1","content":"3\n2 3 1\n2\n1 1 1\n1 0 2"},{"iden":"sample output 1","content":"3\n2\n\nFor 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."},{"iden":"sample input 2","content":"7\n6 3 4 5 2 1 7\n4\n2 2 3\n4 1 2\n0 3 4\n1 2 4"},{"iden":"sample output 2","content":"8\n9\n0\n4"},{"iden":"sample input 3","content":"9\n1 6 7 3 5 8 9 2 4\n10\n5 3 1\n0 7 2\n0 6 3\n1 3 5\n4 0 5\n4 2 3\n1 5 3\n4 5 0\n2 2 5\n2 5 2"},{"iden":"sample output 3","content":"14\n0\n0\n4\n7\n11\n4\n13\n8\n8"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}