310356: CF1821B. Sort the Subarray

B. Sort the Subarraytime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Monocarp had an array $a$ consisting of $n$ integers. He has decided to choose two integers $l$ and $r$ such that $1 \le l \le r \le n$, and then sort the subarray $a[l..r]$ (the subarray $a[l..r]$ is the part of the array $a$ containing the elements $a_l, a_{l+1}, a_{l+2}, \dots, a_{r-1}, a_r$) in non-descending order. After sorting the subarray, Monocarp has obtained a new array, which we denote as $a'$.

For example, if $a = [6, 7, 3, 4, 4, 6, 5]$, and Monocarp has chosen $l = 2, r = 5$, then $a' = [6, 3, 4, 4, 7, 6, 5]$.

You are given the arrays $a$ and $a'$. Find the integers $l$ and $r$ that Monocarp could have chosen. If there are multiple pairs of values $(l, r)$, find the one which corresponds to the longest subarray.

Input

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$);
• the third line contains $n$ integers $a'_1, a'_2, \dots, a'_n$ ($1 \le a'_i \le n$).

Additional constraints on the input:

• the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$;
• it is possible to obtain the array $a'$ by sorting one subarray of $a$;
• $a' \ne a$ (there exists at least one position in which these two arrays are different).

Output

For each test case, print two integers — the values of $l$ and $r$ ($1 \le l \le r \le n$). If there are multiple answers, print the values that correspond to the longest subarray. If there are still multiple answers, print any of them.

ExampleInput

3
7
6 7 3 4 4 6 5
6 3 4 4 7 6 5
3
1 2 1
1 1 2
3
2 2 1
2 1 2

Output

2 5
1 3
2 3

题目大意：
Monocarp有一个由n个整数组成的数组a。他决定选择两个整数l和r，使得1≤l≤r≤n，然后对子数组a[l..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≤t≤10^4)——测试用例的数量。

每个测试用例包含三行:
第一行包含一个整数n(2≤n≤2×10^5);
第二行包含n个整数a1,a2,…,an(1≤ai≤n);
第三行包含n个整数a'1,a'2,…,a'n(1≤a'i≤n)。

输入的附加限制:
所有测试用例的n之和不超过2×10^5;
可以通过对a的一个子数组进行排序得到数组a';
a'≠a(至少存在一个位置，这两个数组是不同的)。

输出：
对于每个测试用例，打印两个整数——l和r的值(1≤l≤r≤n)。如果有多个答案，打印对应最长子数组的值。如果还有多个答案，则打印其中任何一个。题目大意： Monocarp有一个由n个整数组成的数组a。他决定选择两个整数l和r，使得1≤l≤r≤n，然后对子数组a[l..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≤t≤10^4)——测试用例的数量。 每个测试用例包含三行: 第一行包含一个整数n(2≤n≤2×10^5); 第二行包含n个整数a1,a2,…,an(1≤ai≤n); 第三行包含n个整数a'1,a'2,…,a'n(1≤a'i≤n)。 输入的附加限制: 所有测试用例的n之和不超过2×10^5; 可以通过对a的一个子数组进行排序得到数组a'; a'≠a(至少存在一个位置，这两个数组是不同的)。 输出： 对于每个测试用例，打印两个整数——l和r的值(1≤l≤r≤n)。如果有多个答案，打印对应最长子数组的值。如果还有多个答案，则打印其中任何一个。