F. Одно вхождение
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел, и $$$q$$$ запросов к нему. $$$i$$$-й запрос обозначается двумя целыми числами $$$l_i$$$ и $$$r_i$$$. Для каждого запроса надо найти любое целое число, которое входит ровно один раз в подмассиве массива $$$a$$$, начиная с индекса $$$l_i$$$ и заканчивая индексом $$$r_i$$$ (подмассивом называется непрерывный подотрезок массива). Например, если $$$a = [1, 1, 2, 3, 2, 4]$$$, то в запросе $$$(l_i = 2, r_i = 6)$$$ нас интересует подмассив $$$[1, 2, 3, 2, 4]$$$, и возможные ответы на запрос — $$$1$$$, $$$3$$$ и $$$4$$$; а в запросе $$$(l_i = 1, r_i = 2)$$$ нас интересует подмассив $$$[1, 1]$$$, и требуемого элемента не существует.

Можете ли вы ответить на все запросы?

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).

Во второй строке записано $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$).

В третьей строке записано целое число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$).

Затем следуют $$$q$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$l_i$$$ и $$$r_i$$$, обозначающих $$$i$$$-й запрос ($$$1 \le l_i \le r_i \le n$$$).

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

Ответьте на каждый запрос следующим образом:

Если не существует такого целого числа, которое входит в подмассив с индекса $$$l_i$$$ по индекс $$$r_i$$$ ровно один раз, выведите $$$0$$$. Иначе выведите любое такое число.

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