B. Минимизация подотрезков перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ длины $$$n$$$. Вы хотите минимизировать количество подотрезков $$$p$$$, которые являются перестановками. Для этого вы должны выполнить следующую операцию ровно один раз:

  • Выбрать целые числа $$$i$$$, $$$j$$$, где $$$1 \le i, j \le n$$$, затем
  • Поменять местами $$$p_i$$$ и $$$p_j$$$.

Например, если $$$p = [5, 1, 4, 2, 3]$$$ и мы выбираем $$$i = 2$$$, $$$j = 3$$$, то итоговый массив будет равен $$$[5, 4, 1, 2, 3]$$$. Если вместо этого мы выберем $$$i = j = 5$$$, то итоговый массив будет $$$[5, 1, 4, 2, 3]$$$.

При каком выборе $$$i$$$ и $$$j$$$ количество подотрезков, являющихся перестановками, будет минимальным?

Перестановка длины $$$n$$$ — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ является перестановкой, но $$$[1,2,2]$$$ не является перестановкой ($$$2$$$ дважды встречается в массиве), и $$$[1,3,4]$$$ также не является перестановкой ($$$n=3$$$, но в массиве есть $$$4$$$).

Массив $$$a$$$ является подотрезком массива $$$b$$$, если $$$a$$$ можно получить из $$$b$$$ путем удаления нескольких (возможно, нуля или всех) элементов из начала и нескольких (возможно, нуля или всех) элементов из конца.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 2\cdot 10^5$$$) — размер перестановки.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых $$$p_1, p_2, \ldots p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны) — элементы перестановки $$$p$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$) — индексы, которые нужно поменять местами в $$$p$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
8
3
1 2 3
3
1 3 2
5
1 3 2 5 4
6
4 5 6 1 2 3
9
8 7 6 3 2 1 4 5 9
10
7 10 5 1 9 8 3 2 6 4
10
8 5 10 9 2 1 3 4 6 7
10
2 3 5 7 10 1 8 6 4 9
Выходные данные
2 3
1 1
5 2
1 4
9 5
8 8
6 10
5 4
Примечание

В первом примере после замены возможны четыре массива:

  • Если мы поменяем местами $$$p_1$$$ и $$$p_2$$$, то получим массив $$$[2, 1, 3]$$$, который имеет 3 подотрезка, которые являются перестановками ($$$[1]$$$, $$$[2, 1]$$$, $$$[2, 1, 3]$$$).
  • Если поменять местами $$$p_1$$$ и $$$p_3$$$, то получим массив $$$[3, 2, 1]$$$, который имеет 3 подотрезка, которые являются перестановками ($$$[1]$$$, $$$[2, 1]$$$, $$$[3, 2, 1]$$$).
  • Если поменять местами $$$p_2$$$ и $$$p_3$$$, мы получим массив $$$[1, 3, 2]$$$, который имеет 2 подотрезка, которые являются перестановками ($$$[1]$$$, $$$[1, 3, 2]$$$).
  • Если поменять любой элемент местами с самим собой, мы получим массив $$$[1, 2, 3]$$$, который имеет 3 подотрезка, которые являются перестановками ($$$[1]$$$, $$$[1, 2]$$$, $$$[1, 2, 3]$$$).
Поэтому лучше всего поменять местами элементы на позициях $$$2$$$ и $$$3$$$.

В третьем примере, после того, как мы поменяем местами элементы на позициях $$$2$$$ и $$$5$$$, итоговый массив будет равняться $$$[1, 4, 2, 5, 3]$$$. Единственными подотрезками, которые являются перестановками, будут $$$[1]$$$ и $$$[1, 4, 2, 5, 3]$$$. Мы можем показать, что это минимально возможное количество.