Problem Description

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of the sequence $(1,2,\dots,N)$.

Consider the following operation $k\ (k=2,3,\dots,N)$ on this permutation:

• Operation $ k $: For $i=1,2,\dots,k-1$, perform "swap $ P_i $ and $ P_{i+1} $ if $ P_i > P_{i+1} $".

You are also given a non-decreasing sequence $A=(A_1,A_2\dots,A_M)\ (2 \leq A_i \leq N)$ of length $ M $.

For each $i=1,2,\dots,M$, find the number of inversions in $ P $ after applying operations $A_1,A_2,\dots,A_i$ in this order.

The number of inversions in a sequence $x=(x_1,x_2,\dots,x_n)$ is the number of pairs of integers $(i,j)\ (1 \leq i < j \leq n)$ such that $ x_i > x_j $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ P_1 $ $ P_2 $ $\dots$ $ P_N $ $ M $ $ A_1 $ $ A_2 $ $\dots$ $ A_M $

Output Format

Output $ M $ lines. The $ k $-th line should contain the answer for $ i=k $.

Sample Input and Output

Sample Input #1

6
3 2 4 1 6 5
2
4 6

Sample Output #1

3
1

Sample Input #2

20
12 14 16 8 7 15 19 6 18 5 13 9 10 17 4 1 11 20 2 3
15
3 4 6 8 8 9 10 12 13 15 18 18 19 19 20

Sample Output #2

117
116
113
110
108
105
103
99
94
87
79
72
65
58
51

Notes/Hints

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $2 \leq A_i \leq N$
• $ P $ is a permutation of $(1,2,\dots,N)$
• For $i=1,2,\dots,M-1$, $A_i \leq A_{i+1}$ holds
• All input values are integers

Sample Explanation 1

First, operation $ 4 $ is performed. During operation $ 4 $, $ P $ changes as $(3,2,4,1,6,5) \rightarrow (2,3,4,1,6,5) \rightarrow (2,3,4,1,6,5) \rightarrow (2,3,1,4,6,5)$. The number of inversions in $ P $ after operation $ 4 $ is $ 3 $. Then, operation $ 6 $ is performed, and $ P $ eventually changes to $ (2,1,3,4,5,6) $, with the number of inversions being $ 1 $.

见题面 Input 部分

见题面 Output 部分