Permutation Sequence Maintenance

Given a permutation \(a_1, a_2, \dots, a_n\) and an auxiliary sequence \(b_1, b_2, \dots, b_n\) initially all zero, you are to process \(m\) operations. The operations are of two types:

• Modification operation: Given two integers \(l\) and \(r\) (with \(1 \le l \le r \le n\)), for every pair of indices \((i,j)\) satisfying \(l \le i \le j \le r\) and the condition \(a_i \le a_j\) (note that since \(a\) is a permutation the inequality is equivalent to \(a_i < a_j\) when \(i \neq j\)), increment \(b_j\) by \(1\).
• Query operation: Given an index \(x\) (\(1 \le x \le n\)), output the current value of \(b_x\).

The problem requires processing a sequence of \(m\) operations (both modifications and queries) online.

Note: The update for a modification operation can also be seen as: for each index \(j\) in \([l, r]\), increase \(b_j\) by \[ 1 + \#\{i \mid l \le i < j,\, a_i < a_j\}. \]

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of elements in 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\).

Then, \(m\) lines follow. Each line describes an operation in one of the following two formats:

• 1 l r — a modification operation on the interval \([l, r]\).
• 2 x — a query operation asking for the current value of \(b_x\).

outputFormat

For each query operation, output the corresponding value of \(b_x\) on a new line.

sample

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

2
3