CF1821B Sort the Subarray

Monocarp 有一个包含 $n$ 个整数的数组 $a$。他决定选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le n$，然后将子数组 $a[l..r]$（即 $a$ 中从第 $l$ 个到第 $r$ 个元素，包含 $a_l, a_{l+1}, a_{l+2}, \dots, a_{r-1}, a_r$）按非递减顺序排序。排序后，Monocarp 得到了一个新数组，记为 $a'$。 例如，如果 $a = [6, 7, 3, 4, 4, 6, 5]$，Monocarp 选择 $l = 2, r = 5$，那么 $a' = [6, 3, 4, 4, 7, 6, 5]$。 现在给定数组 $a$ 和 $a'$，请你找出 Monocarp 可能选择的 $l$ 和 $r$。如果有多组 $(l, r)$ 满足条件，请输出能得到最长子数组的那一组。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含三行： - 第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。 - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。 - 第三行包含 $n$ 个整数 $a'_1, a'_2, \dots, a'_n$（$1 \le a'_i \le n$）。 输入的额外约束： - 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。 - 一定可以通过对 $a$ 的某个子数组排序得到 $a'$。 - $a' \ne a$（至少有一个位置不同）。

对于每个测试用例，输出两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）。如果有多组答案，输出能得到最长子数组的那一组。如果仍有多组答案，输出其中任意一组即可。

由 ChatGPT 4.1 翻译