题目描述

我现在在 1 楼，电梯在 5 楼，为什么我按了上键，电梯却往下走？

电梯的按钮可以表示成大小为 $n$ 的序列 $x_1,x_2,\cdots,x_n$。

有 $q$ 个操作，分为如下两种类型：

• 1 i y 将 $x_i$ 赋值为 $y$。
• 2 l 求最小的 $d$，使得存在 $l\le a

输入格式

从 $\texttt{elevator.in}$ 读入。

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $x_1,x_2,\cdots,x_n$。

接下来 $q$ 行，每行包含一个操作：

如果第一个整数为 $1$，之后两个整数为 $i,y$。

否则第一个整数为 $2$，之后一个整数 $n$。

输出格式

输出到 $\texttt{elvator.out}$ 中。

对于每个操作二，输出一行，如果有解输出 $d$，否则输出 $-1$。

样例

样例1输入

10 10
1 2 4 3 6 4 5 7 9 10
2 1
2 2
2 3
2 4
2 5
1 2 1
2 1
1 6 8
2 4
2 5

样例1输出

5
7
8
8
9
7
9
10

样例 2

见下发文件中 $\texttt{elevator2.in}$，$\texttt{elvator2.ans}$。

数据范围

保证 $1\le n,q\le5\times10^5,1\le x_i,y\le10^9,1\le i,l\le n$。

下发文件