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

В гримёрке в ряд расположены $$$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$$$ была максимальной. Найдите максимальную возможную схожесть.

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