409012 - 最长连续上升子段

给定 n 个整数,有两种操作: 1.U A B:将第 A 个数替换为 B(下标从 0 开始计数); 2.Q A B:输出区间 [A, B] 内最长连续严格上升子段的长度。

Input

第一行一个整数 T,表示测试用例组数。 每组测试开始是两个整数 n, m(0 < n, m ≤ 10⁵)。 下一行有 n 个整数(0 ≤ val ≤ 10⁵),即初始序列。 接下来 m 行,每行一个操作: U A B(0 ≤ A < n,0 ≤ B ≤ 10⁵) Q A B(0 ≤ A ≤ B < n)

Output

对每个 Q 操作,输出对应区间的答案。

Examples

Input

1
10 10
7 7 3 3 5 9 9 8 1 8 
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9

Output

1
1
4
2
3
1
2
5
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题