Problem Description

You are given a permutation $p_i$ of $1 \sim n$. Then there are $m$ operations, of two types:

1. Swap operation: given $x$, swap the $x$-th number and the $(x+1)$-th number in the current permutation.
2. Query operation: given $k$, find the number of inversions in the current permutation after performing $k$ rounds of bubble sort.

The pseudocode for performing one round of bubble sort on a permutation $p_i$ of length $n$ is:

for i = 1 to n-1:
  if p[i] > p[i + 1]:
    swap(p[i], p[i + 1])

Input Format

The first line contains two integers $n$ and $m$, representing the length of the permutation and the number of operations.

The second line contains $n$ integers representing the permutation $p_i$.

The next $m$ lines each contain two integers $t_i$ and $c_i$, describing an operation:

• If $t_i = 1$, then this operation is a swap operation, and $x = c_i$.
• If $t_i = 2$, then this operation is a query operation, and $k = c_i$.

Output Format

For each query operation, output one line with one integer representing the answer.

3 6
1 2 3
2 0
1 1
1 2
2 0
2 1
2 2

0
2
1
0

Hint

Explanation for Sample 1

First operation: the permutation is $\{1,2,3\}$. After $0$ rounds of bubble sort it is $\{1,2,3\}$, with $0$ inversions.

Second operation: the permutation becomes $\{2,1,3\}$.

Third operation: the permutation becomes $\{2,3,1\}$.

Fourth operation: after $0$ rounds of bubble sort the permutation is $\{2,3,1\}$, with $2$ inversions.

Fifth operation: after $1$ round of bubble sort the permutation becomes $\{2,1,3\}$, with $1$ inversion.

Sixth operation: after $2$ rounds of bubble sort the permutation becomes $\{1,2,3\}$, with $0$ inversions.

Constraints and Notes

For testdata 1 $\sim$ 2: $n, m \leq 100$.

For testdata 3 $\sim$ 4: $n, m \leq 2000$.

For testdata 5 $\sim$ 6: the number of swap operations does not exceed $100$.

For all testdata: $2 \leq n, m \leq 2 \times 10^5$, $t_i \in \{1,2\}$, $1 \leq x < n$, $0 \leq k < 2^{31}$.

Translated by ChatGPT 5