В первой строке дано целое число $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$.
