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:

Modification: 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: 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$ representing a modification operation, or $2, x$ representing a query operation.

$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$.

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