34462번 - Missing Number Queries 서브태스크스페셜 저지다국어

문제

Busy Beaver has an array of positive integers $a_1, \dots, a_N,ドル consisting of positive integers at most $N$. He needs to perform $Q$ operations on the array of two types:

• 1 $x$ $y$: Set $a_x \leftarrow y$.
• 2 $l$ $r$: Output any integer in the range $[1, N]$ that is not found in $a_l, a_{l+1}, \dots, a_r$.

Help answer all of Busy Beaver's queries! The input will be generated in such a way that an answer exists for all type 2 queries.

입력

The first line contains two positive integers $N$ and $Q$ (2ドル \le N \le 2 \cdot 10^5$; 1ドル \le Q \le 2 \cdot 10^5$).

The second line contains $N$ integers $a_1, \dots, a_N$ (1ドル \le a_i \le N$).

Each of the next $Q$ lines contains three positive integers: either 1 $x$ $y$ or 2 $l$ $r$ (1ドル \le x, y \le N$; 1ドル \le l \le r \le N$).

Additional constraint on the input: there is at least one type 2 query, and every type 2 query has an answer.

출력

For each type 2 query, output a single line containing the answer. If there are multiple possible answers for a query, you may output any of them.

제한

서브태스크

노트

In the first query, the only integer from 1ドル$ to 5ドル$ missing from $[3, 5, 2, 1, 5]$ is 4ドル,ドル so 4ドル$ is the only possible answer.

After the second query, the array becomes $[3, 5, 2, 4, 5]$.

After the third query, the array becomes $[3, 5, 1, 4, 5]$.

The last query asks for an integer from 1ドル$ to 5ドル$ missing from $[1, 4, 5]$. Either 2ドル$ or 3ドル$ would be acceptable answers to this query.