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

В гримёрке в ряд расположены $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}
