A. Дореми и краски
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Дореми $$$n$$$ ведерок с краской, они могут быть представленны в виде массива $$$a$$$ длины $$$n$$$. Ведерко $$$i$$$ содержит краску цвета $$$a_i$$$.

Пусть $$$c(l,r)$$$ — количество различных цветов в подмассиве $$$[a_l,a_{l+1},\ldots,a_r]$$$. Выберите $$$2$$$ целых числа $$$l$$$ и $$$r$$$ такие, что $$$l \leq r$$$, а значение $$$r-l-c(l,r)$$$ — максимально возможно.

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

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

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

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

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

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

Для каждого набора входных данных выведите $$$l$$$ и $$$r$$$ такие, что $$$l \leq r$$$, а значение $$$r-l-c(l,r)$$$ — максимально возможно.

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

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

В первом примере $$$a=[1,3,2,2,4]$$$.

  • Если $$$l=1$$$ и $$$r=3$$$, то $$$c(l,r)=3$$$ ($$$3$$$ различных элементов среди $$$[1,3,2]$$$).
  • Если $$$l=2$$$ и $$$r=4$$$, то $$$c(l,r)=2$$$ ($$$2$$$ различных элементов среди $$$[3,2,2]$$$).

Можно показать, что выбор $$$l=2$$$ и $$$r=4$$$ максимизирует значение $$$r-l-c(l,r)$$$, равное $$$0$$$.

Во втором примере $$$a=[1,2,3,4,5]$$$.

  • Если $$$l=1$$$ и $$$r=5$$$, то $$$c(l,r)=5$$$ ($$$5$$$ различных элементов среди $$$[1,2,3,4,5]$$$).
  • Если $$$l=3$$$ и $$$r=3$$$, то $$$c(l,r)=1$$$ ($$$1$$$ различных элементов среди $$$[3]$$$).

Можно показать, что выбор $$$l=1$$$ и $$$r=5$$$ максимизирует значение $$$r-l-c(l,r)$$$, равное $$$-1$$$. Выбор $$$l=3$$$ и $$$r=3$$$ также подходит.