데자 뷰

길이 $10^5$인 배열과 $10^5$가지 종류의 쿼리 $10^5$개가 주어졌을 때 뭔가를 하는, 그런 문제가 아주 많다는 말이 맞을지도 모른다 (어쩌면 너무 많을지도).

- Um_nik

배열 $x_1, x_2, \ldots, x_n$이 주어진다.

이 배열에 두 종류의 쿼리를 수행해야 한다.

• $i$와 $y$가 주어지면 $x_i = y$로 설정한다.
• $l$이 주어지면 $l \leq a < b < c < d$이고 $x_a < x_b < x_c < x_d$인 모든 튜플 $(a,b,c,d)$ 중 가장 작은 $d$를 찾는다. 그러한 튜플이 없으면 없다고 답한다.

첫째 줄에 두 정수 $n, q$가 주어진다 ($1 \leq n,q \leq 500\,000$). $n$은 배열의 원소 수, $q$는 쿼리의 수이다.

둘째 줄에 $n$개의 정수 $x_1, x_2, \ldots, x_n$이 주어진다 ($1 \leq x_i \leq 10^9$).

다음 $q$개의 줄에 각각 쿼리의 설명이 주어진다.

줄의 첫 번째 정수가 $1$이면 다음 두 정수는 $i$와 $y$이며 ($1 \leq i \leq n$, $1 \leq y \leq 10^9$), 첫 번째 종류의 쿼리를 나타낸다.

그렇지 않으면 줄의 첫 번째 정수가 $2$이고 다음 정수는 $l$이며 ($1 \leq l \leq n$), 두 번째 종류의 쿼리를 나타낸다.

두 번째 종류의 쿼리마다 $l \leq a < b < c < d$이고 $x_a < x_b < x_c < x_d$인 모든 튜플 $(a,b,c,d)$ 중 가장 작은 $d$를 출력한다. 그러한 튜플이 없으면 "-1"을 출력한다.