D. Для магов нет ничего сложного в экзамене, но я его не осилил
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Акито надоело быть простым ключником в банке, поэтому он решил поступить в Магическую Академию и стать лучшим магом этого мира! Однако для поступления требовалось решить единственную задачу на экзамене, с которой амбициозный герой никак не может справиться.

В задаче ему давался массив $$$a$$$ длины $$$n$$$. Требовалось минимизировать количество инверсий$$$^{\text{∗}}$$$ в массиве после применения заклинания ровно один раз. Заклинание было простым, для применения Акито должен выбрать два числа $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le n$$$ и выполнить циклический сдвиг подотрезка с $$$l$$$ по $$$r$$$ на один влево.

Более формально, Акито выбирает подотрезок массива $$$[l, r]$$$ и меняет массив следующим образом:

  • Из изначального массива $$$[a_1, a_2, \ldots, a_{l - 1}, \mathbf{ a_l }, \mathbf{ a_{l + 1} } , \mathbf{ \ldots }, \mathbf{ a_{r - 1} }, \mathbf{ a_r }, a_{r + 1}, \ldots, a_{n - 1}, a_n]$$$ он получает массив $$$[a_1, a_2, \ldots, a_{l - 1}, \mathbf{ a_{l + 1} }, \mathbf{ a_{l + 2} }, \mathbf{ \ldots }, \mathbf{ a_{r - 1} }, \mathbf{ a_{r} }, \mathbf{ a_{l} }, a_{r + 1}, \ldots, a_{n - 1}, a_{n}]$$$.

Акито не терпится начать обучение, но он все еще не сдал экзамен. Помогите ему поступить и решите задачу!

$$$^{\text{∗}}$$$Инверсией в массиве $$$b$$$ длины $$$m$$$ называют пару индексов $$$(i, j)$$$, где $$$1 \le i < j \le m$$$ и $$$b_i > b_j$$$. Например, в массиве $$$b = [3, 1, 4, 1, 5]$$$ инверсиями будут являться пары индексов $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(3, 4)$$$.

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

В первой строке ввода дано число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов данных.

В первой строке каждого набора данных дано число $$$n$$$ ($$$1 \le n \le 2000$$$) — длина массива $$$a$$$.

Во второй строке каждого набора данных даны $$$n$$$ чисел $$$a_i$$$ ($$$1 \le a_i \le 2000$$$) — элементы массива $$$a$$$.

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

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

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

Если подходящих пар границ несколько, вы можете вывести любую из них.

Пример
Входные данные
9
7
1 4 3 2 5 3 3
6
1 4 3 2 5 3
8
7 6 5 8 4 3 2 1
10
1 1 1 5 1 1 5 6 7 8
2
1337 69
4
2 1 2 1
3
998 244 353
3
1 2 1
9
1 1 2 3 5 8 13 21 34
Выходные данные
2 7
2 4
1 8
4 6
1 2
1 4
1 3
2 3
5 5
Примечание

В первом примере массив $$$[1, 4, 3, 2, 5, 3, 3]$$$ превратится в массив $$$[1, 3, 2, 5, 3, 3, 4]$$$. Инверсии в нем — это $$$(2, 3)$$$, $$$(4, 5)$$$, $$$(4, 6)$$$ и $$$(4, 7)$$$. Можно показать, что меньше $$$4$$$ инверсий получить нельзя.

Во втором примере массив $$$[1, 4, 3, 2, 5, 3]$$$ превратится в $$$[1, 3, 2, 4, 5, 3]$$$. Инверсии в нем — это $$$(2, 3)$$$, $$$(4, 6)$$$ и $$$(5, 6)$$$. Также подойдут $$$l = 2$$$ и $$$r = 6$$$, тогда массив превратится в $$$[1, 3, 2, 5, 3, 4]$$$, в нем также $$$3$$$ инверсии — $$$(2, 3)$$$, $$$(4, 5)$$$ и $$$(4, 6)$$$. Можно показать, что меньше $$$3$$$ инверсий получить нельзя.

В четвертом примере выбор $$$l = 4$$$ и $$$r = 6$$$ превращает массив в $$$[1, 1, 1, 1, 1, 5, 5, 6, 7, 8]$$$. Он отсортирован, а значит, и инверсий в нем нет.

В последнем примере массив изначально отсортирован, поэтому любая операция над отрезком длины хотя бы $$$2$$$ только увеличит количество инверсий.