您有一个包含 $$$n$$$ 元素的数组 $$$a$$$。数组还有 $$$q$$$ 修改。在第一次修改之前和每次修改之后,您希望了解以下信息:
为了使数组 $$$a$$$ 完全按非降序排序,需要按非降序排序的最小长度子数组是多少?
更正式地说,您想要选择数组 $$$(l, r)$$$ 的子数组,其最小值为 $$$r - l + 1$$$。之后,您将对元素 $$$a_{l}、a_{l + 1}、\ldots、a_{r}$$$ 进行排序,并希望条件 $$$a_{i} \le a_{i + 1}$$$ 对所有 $$$1 \le i < n$$$ 成立。如果数组已经按非降序排序,则 $$$l$$$ 和 $$$r$$$ 应被视为等于 $$$-1$$$。
请注意,找到这样的 $$$(l, r)$$$ 不会以任何方式更改数组。修改本身采用以下形式:为给定的 $$$pos$$$ 和 $$$x$$$ 分配 $$$a_{pos} = x$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{i}$$$ ($$$0 \le |a_{i}| \le 10^{9}$$$) — 数组 $$$a$$$ 的初始元素。
每个测试用例的第三行包含一个数字 $$$q$$$ ($$$0 \le q \le 5 \cdot 10^{5}$$$) — 数组的修改次数。
每个测试用例的以下 $$$q$$$ 行包含两个整数 $$$pos_{i}$$$ ($$$1 \le pos_{i} \le n$$$) 和 $$$val_{i}$$$ ($$$0 \le |val_{i}| \le 10^{9}$$$) - 这意味着对于第 $$$i$$$ 次修改, $$$a_{pos_{i}}$$$ 被分配值$$$val_{i}$$$。
保证所有测试用例的$$$n$$$之和与$$$q$$$之和不超过$$$5 \cdot 10^{5}$$$。
输出
对于每个测试用例,输出 $$$q + 1$$$ 行。每行应包含 $$$2$$$ 整数 $$$l, r$$$ — 最小子数组的边界,这样对其进行排序将使数组 $$$a$$$ 完全排序。如果 $$$a$$$ 已经排序,则输出 $$$l = -1$$$, $$$r = -1$$$。
示例
输入 #1
2 5 2 2 3 4 5 3 2 1 4 1 1 1 5 1 2 3 4 5 9 1 4 2 3 5 2 3 1 1 1 5 1 4 1 3 1 2 1
输出 #1
-1 -1 1 2 1 4 3 4 -1 -1 1 3 1 3 1 5 1 5 2 5 2 5 2 5 2 5 -1 -1
注意
让我们考虑第一个测试用例:
- 最初,数组按非降序排序:$$$[2, 2, 3, 4, 5]$$$
- 第一个查询后,数组如下所示:$$$[\color{red}{2}, \color{red}{1}, 3, 4, 5]$$$。
- 第二次查询后,数组如下所示:$$$[\color{red}{2}, \color{red}{1}, \color{red}{3}, \color{red}{1}, 5]$$$。
- 第三次查询后,数组如下所示:$$$[1, 1, \color{red}{3}, \color{red}{1}, 5]$$$。
红色段表示需要排序的子数组,以便整个数组按非降序排序。