시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB47181445.161%

문제

You have an array $a = (a_1, \ldots, a_n)$ that initially contains a permutation of numbers $1$ through $n$. You have to process queries of two types:

  • "$1$ $p$" ($1 \leq p \leq n$): find $a_p$ in the current array $a$;
  • "$2$ $p$" ($1 \leq p \leq n - 1$): replace $a$ by the result of the function merge applied to arrays $(a_1, \ldots, a_p)$ and $(a_{p + 1}, \ldots, a_n)$.

Function merge can be written in the following way.

func merge(var a as array, var b as array)
     var c as array
     while (a and b have elements)
          if (a[0] > b[0])
               add b[0] to the end of c
               remove b[0] from b
          else
               add a[0] to the end of c
               remove a[0] from a
     while (a has elements)
          add a[0] to the end of c
          remove a[0] from a
     while (b has elements)
          add b[0] to the end of c
          remove b[0] from b
     return c

입력

The first line contains two integers $n$ and $m$ --- the length of the array and the number of queries ($2 \le n, m \le 2 \cdot 10^5$).

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).

Each of the next $m$ lines contains two integers $t_i$ and $p_i$ --- the description of the $i$-th query ($t_i \in \{1, 2\}$, $p$ satisfies the constraints given in the format description above).

출력

For each query of type 1, print the answer on a separate line.

예제 입력 1

4 3
4 3 2 1
2 1
2 1
1 2

예제 출력 1

1

예제 입력 2

5 7
4 3 5 2 1
2 4
2 1
1 3
1 1
2 4
1 4
1 5

예제 출력 2

3
1
3
5