Мы в некотором роде не совсем гавайцы
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Миновав множество опасностей и потеряв студента Лома, экипаж «Беды» прибывает на Гавайи. Предприимчивый директор театра принимает путешественников за артистов и просит выступить в местном театре.

В гримёрке в ряд расположены $$$n$$$ чехлов от контрабасов с высотами $$$a_1, a_2, \ldots, a_n$$$. Несчастный Фукс забыл, какой из чехлов принадлежит ему, поэтому просит вашей помощи.

Назовём схожестью двух мультимножеств количество элементов в их пересечении, например, схожесть мультимножеств $$$\{1, 4, 4, 5\}$$$ и $$$\{2, 4, 5, 7, 11\}$$$ равна $$$2$$$ (пересечение $$$\{4, 5\}$$$), а схожесть мультимножеств $$$\{3, 3, 3\}$$$ и $$$\{1, 3, 3, 3, 4\}$$$ равна $$$3$$$ (пересечение $$$\{3, 3, 3\}$$$). Обратите внимание, что порядок элементов в мультимножестве не имеет значения.

Вам предстоит ответить на $$$q$$$ запросов. Каждый запрос задаёт подотрезок чехлов $$$a_l, a_{l+1}, \ldots, a_r$$$. Вы можете выбрать любое целое число $$$k$$$ ($$$l \le k \le r$$$), чтобы схожесть подотрезка $$$a_l, a_{l+1}, \ldots, a_k$$$ и подотрезка $$$a_{k+1}, \ldots, a_r$$$ была максимальной. Найдите максимальную возможную схожесть.

Вы не понимаете, как такие странные запросы помогут Фуксу с поиском своего чехла, но соглашаетесь помочь.

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

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

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

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

В третьей строке каждого набора дано целое число $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — количество запросов.

В следующих $$$q$$$ строках даны целые числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — запросы поиска максимальной схожести.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$. То же самое гарантируется для $$$q$$$.

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

Для каждого набора входных данных выведите $$$q$$$ целых чисел — ответы на соответствующие запросы.

Пример

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

    281 2 1 3 2 1 2 351 82 73 64 81 494 3 3 3 4 3 1 3 332 91 53 7

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

    3 2 1 2 1 3 2 1