3168. HS的数据结构

【题目背景】

珂朵莉：“我曾经发誓要永远和他在一起，能够如此发誓，让我无比幸福。”

威廉：“我曾经发誓要永远和她在一起，能够如此发誓，让我心获安详。”

珂朵莉：“我曾经认为自己喜欢这个人”

威廉：“我曾经觉得自己非常珍视她”

珂朵莉：“能有如此感受 让我无比幸福”

威廉：“能够如此感受 让我无比喜悦”

珂朵莉：“他曾经对我说 我一定让你幸福”

威廉：“我曾经对她说 我一定会让你幸福”

珂朵莉：“能听到他那样说 让我无比幸福”

威廉：“能够对她那么说 让我心获满足”

珂朵莉：“那个人 分了这么多的幸福给我”

威廉：“我从她那 得到了这么多的东西 可是 我却...”

珂朵莉：“所以 我敢肯定 现在的我... 不管别人怎么说，都一定是世界上最幸福的女孩”

【题目描述】

$HS$ 又开始颓废了，颓着颓着，就想出一道简单的数据结构题！

有一个长度为 $N$ 的序列 $a_1$, $a_2$ ... $a_n$，有 $2$ 种 $M$ 个操作：

$1$ $l$ $r$:查询满足 $l$<=$i$<=$r$ 的 $\min$($a_i$, $r-i+1$) 的最大值

$2$ $x$ $y$:将 $a_x$ 改成 $y$

【输入格式】

第一行两个数 $N$,$M$,第二行 $N$ 个数，第 $i$ 个数表示 $a_i$,接下来 $M$ 行，表示 $M$ 个操作

【输出格式】

若干行表示每一次查询的答案

【样例输入】

5 3
1 2 3 4 5
1 2 4
2 4 1
1 4 5

【样例输出】

2
1

【提示】

对于 $30$% 数据 $1$<=$N$,$M$<=$1000$

对于 $60$% 数据 $1$<=$N$,$M$<=$100000$

对于 $100$% 数据 $1$<=$N$,$M$<=$1000000$ $1$<=$a_i$<=$1000000$