Problem Description

Given a permutation $a_1,\dots,a_n$, you need to maintain a sequence $b_1,\dots,b_n$, with initial values $0$.

There are $m$ operations in total:

• Update operation: given $l,r$, for every pair $(i,j)$ satisfying $l\le i\le j\le r,\;a_i\le a_j$, increase $b_j$ by $1$.
• Query operation: given $x$, query $b_x$.

Input Format

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

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

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

All numbers in the input are integers.

Output Format

For each query operation, output one line containing one integer, which is the answer.

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

0
4
0
3
4
4

Hint

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

For $100\%$ of the testdata, it holds that:

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

Translated by ChatGPT 5