给你一个大小为 $$$n$$$ 的数组 $$$a$$$。
仅当满足以下条件时,线段 $$$[l, r](1 \le l < r \le n)$$$ 才称为多边形线段:
- $$$(r-l+1) \geq 3$$$;
- 考虑 $$$a_l, a_{l+1}, \ldots, a_r$$$ 作为边长,这些边可以形成具有 $$$(r-l+1)$$$ 边的多边形。
处理两种类型的 $$$q$$$ 查询:
- "1 l r": 求所有多边形线段$$$[l_0,r_0]$$$中最长线段的长度,满足$$$l \le l_0 \le r_0 \le r$$$。如果没有这样的多边形线段,则输出$$$-1$$$;
- "2 i x": 赋值 $$$a_i := x$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
对于每个测试用例:
- 每个测试用例的第一行包含两个整数 $$$n$$$, $$$q$$$ ($$$4 \le n \le 2\cdot 10^5$$$, $$$1 \le q \le 10^5$$$);
- 每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$);
- 以下 $$$q$$$ 行包含查询的描述。每行属于以下两种类型之一:“1 l r”($$$1 \le l < r \le n$$$, $$$r-l+1\ge 3$$$); “2 i x”($$$1 \le i \le n$$$,$$$1 \le x \le 10^{12}$$$)。
保证所有测试用例的$$$n$$$总和不会超过$$$2 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不会超过$$$10^5$$$。
输出
对于每个查询,如果没有合适的段,则在新行中输出$$$-1$$$。否则,在新行中输出满足上述条件的最长线段的长度。
示例
输入 #1
2 5 6 3 1 2 2 8 1 1 3 1 1 4 1 1 5 2 1 5 1 1 4 1 1 5 4 10 500000000000 500000000000 1000000000000 500000000000 1 1 3 1 2 4 1 1 4 2 1 499999999999 2 3 999999999999 1 1 3 1 2 4 1 1 4 2 3 1000000000000 1 1 3
输出 #1
-1 4 4 3 5 -1 -1 4 -1 3 4 -1
注意
在第一个测试用例的第一个查询中,在给定条件下不存在多边形线段。例如,考虑线段 $$$[1,3]$$$,您无法形成边长为 $$$a_1=3$$$、$$$a_2=1$$$ 和 $$$a_3=2$$$ 的三角形。
在第一个测试用例的第二个查询中,最长的多边形线段是$$$[1,4]$$$。您可以形成边长为 $$$a_1=3$$$、$$$a_2=1$$$、$$$a_3=2$$$ 和 $$$a_4=2$$$ 的四边形。
边长为 $$$3$$$、$$$1$$$、$$$2$$$ 和 $$$2$$$ 的四边形示例。