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.