시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 1 1 1 100.000%

문제

You may be right that there are a lot (maybe even too many) problems of kind ``given array of length $10^5$ and $10^5$ queries of $10^5$ different types, do some...

- Um_nik

You are given an array $x_1, x_2, \ldots, x_n$.

You need to perform two types of queries on this array.

  • Given $i$ and $y$, set $x_i = y$.
  • Given $l$, find the smallest $d$ among all tuples $(a,b,c,d)$ with $l \leq a < b < c < d$ and $x_a < x_b < x_c < x_d$, or reply that there are no such tuples.

입력

The first line contains two integers $n,q$ ($1 \leq n,q \leq 500\,000$): the number of elements in the array and the number of queries.

The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \leq x_i \leq 10^9$).

Each of the next $q$ lines contains the description of a query.

If the first integer in the line is equal to $1$, then the next two integers are $i$ and $y$ ($1 \leq i \leq n$, $1 \leq y \leq 10^9$), describing a query of the first type.

Otherwise, the first integer in the line is equal to $2$, and the next integer is equal to $l$ ($1 \leq l \leq n$), describing a query of the second type.

출력

For each query of the second type, return the smallest $d$ among all tuples $(a,b,c,d)$ such that $l \leq a < b < c < d$ and $x_a < x_b < x_c < x_d$, or print "-1" if there are no such tuples.

예제 입력 1

11 10
1 2 3 4 5 10 9 8 7 6 8
2 1
1 3 2
2 1
1 1 2
2 1
2 5
2 6
1 9 6
1 10 7
2 5

예제 출력 1

4
5
6
-1
-1
11