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

Определим оценку произвольного массива $$$b$$$ как длину $$$b$$$ минус количество различных элементов в $$$b$$$. Например:

  • Оценка массива $$$[1, 2, 2, 4]$$$ равна $$$1$$$, так как его длина равна $$$4$$$, и в нём $$$3$$$ различных элемента ($$$1$$$, $$$2$$$, $$$4$$$).
  • Оценка массива $$$[1, 1, 1]$$$ равна $$$2$$$, так как его длина равна $$$3$$$, а различных элементов всего $$$1$$$ ($$$1$$$).
  • Пустой массив имеет оценку $$$0$$$.

У вас есть массив $$$a$$$. Вам нужно не более одного раза удалить некоторый непустой непрерывный подмассив из $$$a$$$.

Более формально, вы можете сделать следующее не более одного раза:

  • выбрать два целых числа $$$l$$$, $$$r$$$, где $$$1 \le l \le r \le n$$$, и
  • удалить непрерывный подмассив $$$[a_l,\ldots,a_r]$$$ из $$$a$$$ (то есть заменить $$$a$$$ на $$$[a_1,\ldots,a_{l - 1},a_{r + 1},\ldots,a_n]$$$).

Найдите операцию, в результате которой оценка $$$a$$$ будет максимальной. Если есть несколько ответов, выведите тот, который минимизирует финальную длину $$$a$$$ после операции. Если всё ещё есть несколько ответов, вы можете вывести любой из них.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$).

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

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

Для каждого набора входных данных, если вы не хотите применять операцию, выведите $$$0$$$.

В противном случае выведите два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), представляющих левую и правую границы удаленного подмассива.

Удалённый подмассив должен быть выбран так, чтобы оценка была максимальна, а среди всех таких ответов выберите любой, который минимизирует финальную длину массива.

Пример
Входные данные
3
1
1
5
1 1 1 1 1
4
2 1 3 2
Выходные данные
1 1
0
2 3
Примечание

В первом наборе входных данных у нас есть два варианта:

  • ничего не делать: оценка $$$[1]$$$ равна $$$1-1=0$$$.
  • удалить подмассив с $$$l=1$$$, $$$r=1$$$: мы удаляем единственный элемент и получаем пустой массив с оценкой $$$0$$$.
Таким образом, максимальная возможная оценка равна $$$0$$$. Однако, поскольку нам нужно дополнительно минимизировать финальную длину массива, мы должны вывести второй вариант с $$$l=r=1$$$. Обратите внимание, что первый вариант ничего не делать является неправильным, так как для него финальная длина больше.

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

В третьем наборе входных данных выбран подмассив $$$[2, \color{red}1, \color{red}3, 2]$$$, после чего $$$a$$$ становится $$$[2, 2]$$$. Он имеет длину $$$2$$$ и $$$1$$$ различный элемент, так что его оценка равна $$$2 - 1 = 1$$$. Можно доказать, что это самый короткий массив, который максимизирует оценку.