B. Отсортируй подмассив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа был массив $$$a$$$ из $$$n$$$ целых чисел. Он решил выбрать два целых числа $$$l$$$ и $$$r$$$, такие, что $$$1 \le l \le r \le n$$$, и отсортировать подмассив $$$a[l..r]$$$ (подмассив $$$a[l..r]$$$ — это подотрезок массива $$$a$$$, содержащий элементы $$$a_l, a_{l+1}, a_{l+2}, \dots, a_{r-1}, a_r$$$) в порядке неубывания. После сортировки подмассива Монокарп получил новый массив, который мы обозначим за $$$a'$$$.

Например, если $$$a = [6, 7, 3, 4, 4, 6, 5]$$$, и Монокарп выбрал $$$l = 2, r = 5$$$, то $$$a' = [6, 3, 4, 4, 7, 6, 5]$$$.

Вам даны массивы $$$a$$$ и $$$a'$$$. Найдите такие целые числа $$$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$$$). Если ответов несколько, выведите пару чисел, соответствующую наиболее длинному подмассиву. Если ответов все еще несколько, выведите любой из них.

Пример
Входные данные
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
Выходные данные
2 5
1 3
2 3