33265번 - Find And Modify 다국어

문제

You are given a permutation $a_1, \ldots, a_n$. You need to maintain a sequence $b_1, \ldots, b_n$ initialized by zeroes. Process $m$ operations of the following form:

• Modification operation: given $\ell$ and $r,ドル for each pair $(i, j)$ such that $\ell \leq i \leq j \leq r$ and $a_i \leq a_j,ドル increment $b_j$ by 1ドル$;
• Query operation: given $x,ドル return $b_x$.

입력

The first line of input contains two integers $n$ and $m$ (1ドル \leq n, m \leq 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, \ldots, a_n$ (1ドル \leq a_i \leq n$; all $a_i$ are distinct).

Each of the next $m$ lines consists of integers and has either the form "1~$\ell$~$r$" for a modification operation or the form "2~$x$" for a query operation (1ドル \leq \ell \leq r \leq n$; 1ドル \leq x \leq n$).

You may assume that the input contains at least one query operation.

출력

For each query operation, output one line containing an integer that represents the answer.

제한

힌트