咖啡的罪恶

Problem Description

Koyuki 通过出售梦境转移器赚到了一大笔钱，只可惜她在走廊里不慎撞到了拿着咖啡的 Noa，导致 Noa 手上的文件洒满了咖啡。更严重的是，这些文件是 Noa 特意为老师准备的。现在，她决定没收 Koyuki 的所得，并要求她完成下面的题目。 Noa 定义一个长度为 $\epsilon+1$ 的非负整数序列 $a_\delta,a_{\delta+1},a_{\delta+2},\cdots,a_{\delta+\epsilon}$（$\delta$ 为非负整数）是一个 咖啡序列 当且仅当所有整数 $i$（$0\le i\le\epsilon$）均满足其在序列中的出现次数恰好为 $a_{\delta+i}$。 她给定了一个长度为 $n$ 的非负整数序列 $b_1,b_2,b_3,\cdots,b_n$，并要求 Koyuki 完成 $q$ 次操作。每次操作形如：

1. 1 x p（操作 1）：令 $b_x:=p$。
2. 2 l r（操作 2）：对于所有满足 $l\le L\le R\le r$ 的咖啡序列 $b_L,b_{L+1},b_{L+2},\cdots,b_R$，计算它的长度（也就是 $R-L+1$）的最大值。若不存在任何满足条件的咖啡序列，则最大值为 $0$。 Koyuki 注意到身旁的你正在打程序设计竞赛，于是顺手将题目扔给了你。当你转过头时，只隐约看见她跑去的背影。Noa 向你道了歉，并保证假如你做出了这道题目，她就会带 Koyuki 亲自来道歉。

Input

本题包含多组测试数据。 来自 Noa 的温馨提示：本题输入输出量较大，对于使用 C++ 语言参加竞赛的选手，强烈建议使用关闭同步流的 cin 和 cout 完成输入输出。 首先在第一行输入一个整数 $T$（$1\le T\le10$）表示测试数据组数。 对于每一组测试数据，输入包含 $q+2$ 行。 第一行包含两个整数 $n,q$（$1\le n,q\le2\times10^5$），分别表示序列的长度和操作的次数。 第二行包含 $n$ 个整数 $b_1,b_2,b_3,\cdots,b_n$（$0\le b_1,b_2,b_3,\cdots,b_n\le n$）表示序列的元素。 接下来 $q$ 行，每行首先包含一个整数 $op$（$1\le op\le 2$）表示操作的类型，接下来包含两个整数 $x,p$ 或 $l,r$ 表示一次操作。 保证在所有操作 1 中，$op=1$，$1\le x\le n$，$0\le p\le n$。保证在所有操作 2 中，$op=2$，$1\le l\le r\le n$。

Output

对于每一组测试数据，对于每一次操作 2，输出包含一行一个整数表示满足条件的咖啡序列的长度最大值。若不存在，则答案为 $0$。

Sample Input

1
12 8
2 1 2 0 0 3 2 1 1 0 0 0
2 1 4
2 1 5
2 1 6
2 1 10
2 1 12
2 6 12
1 2 0
2 1 4

Sample Output

0
5
5
5
7
7
4

Hint

在样例的测试数据中，共有 $8$ 次操作：

1. 第 $1$ 次操作的类型为操作 2，$l=1,r=4$。答案为 $0$。
2. 第 $2,3,4$ 次操作的类型为操作 2，$l=1,r=5/6/10$。在 $L=1,R=5$ 时，序列 $b_1=2,b_2=1,b_3=2,b_4=0,b_5=0$ 是咖啡序列。答案均为 $5$。
3. 第 $5,6$ 次操作的类型为操作 2，$l=1/6,r=12$。在 $L=6,R=12$ 时，序列 $b_6=3,b_7=2,b_8=1,b_9=1,b_{10}=0,b_{11}=0,b_{12}=0$ 是咖啡序列。答案均为 $7$。
4. 第 $7$ 次操作的类型为操作 1，$x=2,p=0$。此时 $b_2:=0$。
5. 第 $8$ 次操作的类型为操作 2，$l=1,r=4$。在 $L=1,R=4$ 时，序列 $b_1=2,b_2=0,b_3=2,b_4=0$ 是咖啡序列。答案为 $4$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）