Bubble Sort Rounds and Inversion Count

You are given a permutation \(p_1, p_2, \ldots, p_n\) of the numbers \(1 \sim n\). There are \(m\) operations to be performed on this permutation. There are two types of operations:

• Swap operation: Given an integer \(x\), swap the element at position \(x\) with the element at position \(x+1\) in the current permutation.
• Query operation: Given an integer \(k\), calculate the number of inversion pairs after performing \(k\) rounds of bubble sort on the current permutation.

The pseudocode for one round of bubble sort on an array of length \(n\) is as follows:

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

Recall that an inversion pair in an array \(p\) is a pair of indices \((i,j)\) with \(1 \le i p[j]\). Note that after at most \(n\) rounds of bubble sort, the permutation will be sorted, and the inversion count will be zero.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the size of the permutation and the number of operations.

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\) representing the initial permutation of \(1 \sim n\).

The following \(m\) lines describe the operations. Each operation is given in one of the following two formats:

• 1 x: A swap operation, which means swap the element at position \(x\) with the element at position \(x+1\) (positions are 1-indexed).
• 2 k: A query operation, which asks for the number of inversion pairs after performing \(k\) rounds of bubble sort on the current permutation.

outputFormat

For each query operation, output a single line containing the inversion count after performing the corresponding \(k\) rounds of bubble sort on the current permutation.

sample

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

2
2