Given a permutation $a_1, \dots, a_n$ of $1, \dots, n$.

There are $m$ operations. Each operation provides an integer $x$. First, perform a modification: reverse the prefix $a_1, a_2, \dots, a_x$ to $a_x, \dots, a_2, a_1$. Then, query the number of pairs $(i, j)$ such that $1 \le i < j \le x$ and $a_i < a_j$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing $a_1, \dots, a_n$.

The next $m$ lines each contain an integer $x$, representing an operation.

Output

Output $m$ lines, each containing an integer representing the answer to the query after each operation.

Examples

Input 1

6 5
5 4 2 3 1 6
3
5
6
3
6

Output 1

3
6
4
2
10

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

All values are integers.

For $100\%$ of the data, $1 \le a_i \le n$, $1 \le x \le n$, $1 \le n \le 2 \times 10^5$, and $1 \le m \le 5 \times 10^4$.