Given a permutation $a_1, \dots, a_n$, you need to maintain a sequence $b_1, \dots, b_n$, initially all zeros.

There are $m$ operations in total:

Update operation: Given $l, r$, for every pair $(i, j)$ such that $l \le i \le j \le r$ and $a_i \le a_j$, increment $b_j$ by $1$.

Query operation: Given $x$, query the value of $b_x$.

Input

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

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

The next $m$ lines each contain either $1, l, r$ or $2, x$, representing an update operation or a query operation, respectively.

All input values are integers.

Output

For each query operation, output one line containing a single integer representing the answer.

Examples

Input 1

8 10
5 4 8 7 1 6 3 2
1 2 5
2 8
1 2 8
1 7 8
2 4
2 1
2 6
2 4
1 8 8
2 4

Output 1

0
4
0
3
4
4

Subtasks

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $100\%$ of the data, the following constraints are satisfied:

$1 \le n, m \le 2 \times 10^5$;

$1 \le a_i \le n$, and all $a_i$ are distinct;

$1 \le l \le r \le n$;

$1 \le x \le n$.