题目背景

我们处在泪海的两端

越是靠近 越是不安

我不想剪断 我的世界太混乱

为你写下的诗 停不在你耳畔

——MOCKER44. / 洛天依《欲泪海》

题目描述

小 X 和小 Z 在研究排列。

他们弄丢了一个排列 $p$，不过小 Z 还记得其长度 $n$，以及每个数前面比它大的数字个数，即 $b_i=\sum_{j=1}^{i-1}[p_j\gt p_i]$。

然而小 Z 的记忆有偏差，在追忆过程中，他会修改 $b_i$ 的值。小 X 还会询问当前某个 $p_i$ 的值，请你回答他的询问。此时保证存在合法排列，若有多种可能值，输出其中最小的那个。

输入格式

第一行两个整数 $n,q$，表示排列长度和操作次数。

第二行 $n$ 个整数，表示初始的 $b_i$。

接下来 $q$ 行，每行一个操作，分为以下两种：

• $1\ i\ x$：将 $b_i$ 修改为 $x$。
• $2\ i$：查询可能的最小 $p_i$。

输出格式

对每个 $2$ 操作输出一行一个整数，表示可能的最小 $p_i$。

输入 #1

3 7
0 0 0
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3

输出 #1

1
2
3
2
1
3

输入 #2

5 15
0 1 2 3 4
2 1
2 2
1 2 1
2 2
2 3
2 5
1 3 0
1 4 0
2 3
2 4
2 5
1 4 1
2 3
2 4
2 5

输出 #2

5
4
4
3
1
4
5
1
5
4
1

说明/提示

对于所有数据，$1\le n,q\le 2\times 10^5,0\le b_i\lt i$。

出于节约评测资源的考虑，本题开启子任务测试及依赖。

\begin{array}{|c|c|c|} \hline \textbf{子任务} & n,q\le & \textbf{特殊性质}& \textbf{分数} & \textbf{子任务依赖}\\ \hline 1 & 7 & \textbf{无} & 5 &\textbf{无}\\ \hline 2 & 500 & \textbf{无}& 5 &1\\ \hline 3 & 2000 & \text{A} & 5 &\textbf{无}\\ \hline 4 & 2000 & \text{B} & 5 &\textbf{无} \\ \hline 5 & 2000 & \textbf{无} & 10 & 2,3,4\\ \hline 6 & 2\times 10^4 & \textbf{无} & 15 & 5\\ \hline 7 & 10^5 & \text{A} & 10 & 3\\ \hline 8 & 10^5 & \text{B} & 10 & 4\\ \hline 9 & 10^5 & \textbf{无} & 15 & 6,7,8\\ \hline 10 & 1.5\times 10^5 & \textbf{无} & 10 & 9\\ \hline 11 & 2\times 10^5 & \textbf{无} & 10 & 10\\ \hline \end{array}

特殊性质 A：不存在 $1$ 操作。

特殊性质 B：$i-b_i\le 20$。