시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB130664.615%

## 문제

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