18910번 - Deja Vu 다국어

문제

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.

제한

힌트