Permutation Maintenance on Sequence B

You are given a permutation (a_1, a_2, \dots, a_n) and need to maintain a sequence (b_1, b_2, \dots, b_n) initially all zeros. You have to process (m) operations.

There are two types of operations:

• Update operation: Given two integers \(l\) and \(r\), for every pair of indices \((i, j)\) satisfying \(l \le i \le j \le r\) and \(a_i \le a_j\), increase \(b_j\) by 1. In other words, for every index \(j\) in \([l, r]\), add \(\displaystyle \sum_{i=l}^{j} \mathbb{1}_{\{a_i \le a_j\}}\) to \(b_j\).
  
• Query operation: Given an integer \(x\), output the current value of \(b_x\).

Note: The indices are 1-indexed.

inputFormat

The first line contains two integers (n) and (m) denoting the size of the permutation and the number of operations, respectively.

The second line contains (n) space-separated integers representing the permutation (a_1, a_2, \dots, a_n).

Each of the next (m) lines represents an operation in one of the following formats:

• If the line starts with the integer 1, it is an update operation. It is followed by two integers \(l\) and \(r\).
• If the line starts with the integer 2, it is a query operation. It is followed by a single integer \(x\).

It is guaranteed that all operations are valid.

outputFormat

For each query operation, output a single line containing the value of (b_x) after processing the operations in order.

sample

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

3
3
1

</p>