\begin{problem}{Мы в некотором роде не совсем гавайцы}{стандартный ввод}{стандартный вывод}{5 секунд}{256 мегабайт}

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

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

Назовём \textit{схожестью} двух мультимножеств количество элементов в их пересечении, например, \textit{схожесть} мультимножеств $\{1, 4, 4, 5\}$ и $\{2, 4, 5, 7, 11\}$ равна $2$ (пересечение $\{4, 5\}$), а \textit{схожесть} мультимножеств $\{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$), чтобы \textit{схожесть} подотрезка $a_l, a_{l+1}, \ldots, a_k$ и подотрезка $a_{k+1}, \ldots, a_r$ была \textbf{максимальной}. Найдите максимальную возможную \textit{схожесть}.

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

\begin{center}
\includegraphics{pic5.png}
\end{center}


\InputFile
В первой строке дано целое число $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$)~--- запросы поиска максимальной \textit{схожести}.

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


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


\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\end{problem}

