Problem Description

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

There are $m$ operations. In each operation, an integer $x$ is given. First, perform a modification: reverse $a_1, a_2, \dots, a_x$ into $a_x, \dots, a_2, a_1$. Then query how many distinct pairs $(i, j)$ satisfy $1 \le i < j \le x$ and $a_i < a_j$.

Input Format

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

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

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

Output Format

Output $m$ lines. Each line contains one integer, representing the answer to the query for each operation in order.

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

3
6
4
2
10

Hint

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

All values are integers.

Constraints: for $100\%$ of the testdata, $1 \le a_i \le n$, $1 \le x \le n$, $1 \le n \le 2 \times 10^5$, $1 \le m \le 5 \times 10^4$.

Translated by ChatGPT 5