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.