AT_arc204_c [ARC204C] Maximize Sum of Mex

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**.

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 $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 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. ### 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.