D. Найди различные!
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел, а также $$$q$$$ запросов.

Каждый запрос представлен двумя числами $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$). Ваша задача для каждого запроса найти такие два индекса $$$i$$$ и $$$j$$$ (или сообщить, что их не существует), что:

  • $$$l \le i \le r$$$;
  • $$$l \le j \le r$$$;
  • $$$a_i \ne a_j$$$.

Иными словами, вам нужно для каждого запроса найти пару различных элементов среди $$$a_l, a_{l+1}, \dots, a_r$$$ или сообщить, что такой пары не существует.

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

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

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.

Третья строка каждого набора содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Следующие $$$q$$$ строк содержат по два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$) — границы запроса.

Гарантируется, что сумма значений $$$n$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$. Аналогично, гарантируется, что сумма значений $$$q$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите два числа: искомые $$$i$$$ и $$$j$$$ ($$$l \le i, j \le r$$$), для которых $$$a_i \ne a_j$$$. Если такой пары не существует, выведите $$$i=-1$$$ и $$$j=-1$$$.

Вы можете разделять выводы для наборов входных данных пустыми строками. Это не является обязательным требованием.

Пример
Входные данные
5
5
1 1 2 1 1
3
1 5
1 2
1 3
6
30 20 20 10 10 20
5
1 2
2 3
2 4
2 6
3 5
4
5 2 3 4
4
1 2
1 4
2 3
2 4
5
1 4 3 2 4
5
1 5
2 4
3 4
3 5
4 5
5
2 3 1 4 2
7
1 2
1 4
1 5
2 4
2 5
3 5
4 5
Выходные данные
2 3
-1 -1
1 3

2 1
-1 -1
4 2
4 6
5 3

1 2
1 2
2 3
3 2

1 3
2 4
3 4
5 3
5 4

1 2
4 2
1 3
2 3
3 2
5 4
5 4