对于由 $$$m$$$ 整数组成的序列 $$$b$$$,集合 $$$S(b)$$$ 被定义为满足以下条件的元组 $$$(i,j,k)$$$ 的集合:
- $$$i$$$、$$$j$$$、$$$k$$$ 是整数;
- $$$1 \le k \lt m$$$;
- $$$1 \le i \lt j \le m-k+1$$$;
- 对于 $$$b$$$ 中的每个元素 $$$v$$$,$$$v$$$ 在 $$$[b_i,b_{i+1},\ldots,b_{i+k-1}]$$$ 和 $$$[b_j,b_{j+1},\ldots,b_{j+k-1}]$$$ 中出现的次数相同。
例如,当 $$$b=[1,2,1,2]$$$ 时,元组 $$$(1,3,2)$$$ 是 $$$S(b)$$$ 的元素,因为 $$$1$$$ 和 $$$2$$$ 在 $$$[b_1,b_2]$$$ 和 $$$[b_3,b_4]$$$ 中都出现一次。
此外,我们在正整数序列上定义了两个函数:
- $$$k_\max(b)$$$ 定义为 $$$S(b)$$$ 的所有元素 $$$(i,j,k)$$$ 上 $$$k$$$ 的最大值;
- $$$f(b)$$$ 定义为 $$$S(b)$$$ 的不同元素 $$$(i,j,k)$$$ 的数量,使得 $$$k=k_\max(b)$$$。
异常,当 集合 $$$S(b)$$$ 为空,它们被定义为 $$$k_\max(b)=0$$$ 和 $$$f(b)=0$$$。
给定一个由 $$$n$$$ 整数组成的序列 $$$a$$$。请回答以下类型的 $$$q$$$ 询问:
- $$$i\;x$$$:将 $$$a_i$$$ 的值更改为 $$$x$$$。然后,找到 $$$k_\max(a)$$$ 和 $$$f(a)$$$ 的值。
请注意,更新是持久的。换句话说,一个查询的更新也会影响后面的查询。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 100\,000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$)。
以下 $$$q$$$ 行中的每一行都包含两个整数 $$$i_j$$$ 和 $$$x_j$$$ 表示第 $$$j$$$ 查询 ($$$1 \le i_j,x_j \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$100\,000$$$。
输出
对于每个测试用例,输出 $$$q$$$ 行。
在第 $$$j$$$ 行,您必须为第 $$$j$$$ 查询输出 $$$k_\max(a)$$$ 和 $$$f(a)$$$ 的值。
可以证明,在该问题的约束下,两个值都不会超过 $$$10^{11}$$$。
示例
输入复制
45 31 2 3 4 53 24 15 24 31 2 1 14 23 22 15 21 3 2 4 55 35 58 31 2 3 4 1 2 5 47 37 42 1
输出复制
1 13 13 32 32 11 23 10 04 104 44 2
注意
紧接着第二个测试用例的第一个查询之后,$$$a=[1,2,1,2]$$$。集合$$$S(a)$$$的元素如下:
- $$$(1,3,1)$$$: $$$[\color{红色}{1},2,\color{蓝色}{1},2]$$$;
- $$$(2,4,1)$$$: $$$[1,\color{红色}{2},1,\color{蓝色}{2}]$$$;
- $$$(1,2,2)$$$: $$$[\color{红色}{1},\color{洋红色}{2},\color{蓝色}{1},2]$$$;
- $$$(1,3,2)$$$: $$$[\颜色{红色}{1},\颜色{红色}{2},\颜色{蓝色}{1},\颜色{蓝色}{2}]$$$;
- $$$(2,3,2)$$$: $$$[1,\color{红色}{2},\color{洋红色}{1},\color{蓝色}{2}]$$$。
因此,$$$k_\max(a)=2$$$,并且$$$f(a)=3$$$,因为存在三个元素$$$(i,j,k)$$$,其中$$$k=k_\max(a)=2$$$。
紧接着第三个测试用例的第二个查询,$$$a=[1,3,2,4,5]$$$。此时集合 $$$S(a)$$$ 为空。
根据定义,您应该输出 $$$k_\max(a)=0$$$ 和 $$$f(a)=0$$$,因为 $$$S(a)$$$ 当前为空。