CF1982F.Sorting Problem Again

已知一个序列，给定 $q$ 次修改。对于初始序列和每次修改后的序列，你需要做到：

找到长度最小的连续的子串，使得如果这个子串按升序排序，整个序列也就满足单调不降。输出这个子串的起始位置 $l, r$；若此时序列已经满足单调不降，认为 $l, r$ 均为 $-1$。

注意，对这个子串的“升序排序”只是一个假想出的操作，并不会改变原序列。

本题有多组数据。

第一行输入一个正整数 $T$（$1 \leq T \leq 10$），表示测试数据的组数。对于每组数据：

第一行输入序列长度 $n$（$1 \leq n \leq 5 \cdot 10^5$）。

第二行输入 $n$ 个整数 $a_i$，即给定的序列（$0 \leq |a_i| \leq 10^9$）。

第三行输入修改操作的个数 $q$（$0 \leq q \leq 5 \cdot 10^5$）。

接下来 $q$ 行，每行输入两个整数 $p$ 和 $v$（$1 \leq p \leq n$ 且 $0 \leq |v| \leq 10^9$），表示 $a_p \gets v$。

保证 $\sum n, \sum q \leq 5 \cdot 10^5$。

对于每组测试数据，输出 $q + 1$ 行。

每行输出两个整数 $l, r$，含义见题面。

对于第一个样例：

• 一开始，序列 $a$ 已经满足单调不降：$[2, 2, 3, 4, 5]$。
• 第一次修改后，序列 $a$ 长这样：$[\color{red}{2}\color{black}{}, \color{red}{1}\color{black}{}, 3, 4, 5]$。
• 第二次修改后，序列 $a$ 长这样：$[\color{red}{2}\color{black}{}, \color{red}{1}\color{black}{}, \color{red}{3}\color{black}{}, \color{red}{1} \color{black}{},5]$。
• 第三次修改后，序列 $a$ 长这样：$[1, 1, \color{red}{3}\color{black}{}, \color{red}{1}\color{black}{}, 5]$。

标红的部分即为题目所求。