Problem Statement

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

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

• Operation $k$: For $i=1,2,\dots,k-1$ in this order, if $P_i > P_{i+1}$, swap the values of the $i$-th and $(i+1)$-th elements of $P$.

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 inversion number of $P$ after applying the operations $A_1, A_2, \dots, A_i$ in this order.

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

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)$.
• $A_i \leq A_{i+1}$ for $i=1,2,\dots,M-1$.
• 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
M
A_1 A_2 \dots A_M

Output

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