安德烈记得他有$$$n$$$块,编号从$$$1$$$到$$$n$$$。在编号为$$$i$$$的块上,最初写入了一个整数$$$a_i$$$。他按照编号递增的顺序将它们排成一排:首先是编号为 $$$1$$$ 的块,然后是编号为 $$$2$$$ 的块,依此类推,最后是编号为 $$$n$$$ 的块。
对于连续块 $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) 的某个段,我们称一个整数 $$$d\ (0 \le d \le r-l)$$$ 讨厌 如果 $$$\min(a_l, a_{l+1}, \ldots, a_{l+d}) = d$$$。
Andrey 很好奇,所以他想执行以下两种类型之一的 $$$q$$$ 操作:
- 将第$$$i$$$块上写入的数字$$$a_i$$$更改为$$$x$$$。
- 确定 肮脏 段 $$$[l,\ r]\ (1 \le l \le r \le n)$$$ 的 。段的肮脏度是指给定段的肮脏数字 $$$d\ (0 \le d \le r-l)$$$ 的数量。
Andrey 无法弄清楚如何快速处理这些查询,因此他向您寻求帮助。帮助他执行上述操作!
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \le n, q \le 2 \cdot 10^5)$$$ — 分别是块数和操作数。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 2 \cdot 10^5)$$$ — 写在块上的初始数字。
以下 $$$q$$$ 行描述了要执行的操作。
每行以整数 $$$idx$$$ $$$(1 \le idx \le 2)$$$ — 操作类型。
如果 $$$idx = 1$$$,则后面是两个整数 $$$i$$$ $$$(1 \le i \le n)$$$ 和 $$$x$$$ $$$(1 \le x \le 2 \cdot 10^5)$$$ — 第一种操作的描述。
如果 $$$idx = 2$$$,则后面跟着两个整数 $$$l$$$ 和 $$$r$$$ $$$(1 \le l \le r \le n)$$$ — 第二种操作类型的描述。
保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,对于第二类型的每个操作,打印一个表示该段的肮脏程度的整数。
示例
输入复制
15 51 2 3 4 52 1 51 1 51 2 51 3 12 1 5
输出复制
10