Частые значения

Задана последовательность $n$ целых чисел $a_1,a_2,...,a_n$ в неубывающем порядке. Вам также заданы несколько запросов, состоящих из индексов $i$ и $j(1\le i\le j\le n)$. Для каждого запроса определите число, которое чаще всего встречается среди $a_i,...,a_j$.

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

Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа $n$ и $q(1\le n,q\le 10^5)$. Следующая строка содержит $n$ целых чисел $a_1,a_2,...,a_n(-10^5\le a_i\le 10^5)$. Считайте, что для каждого $i\in 1,...,n-1:a_i\le a_{i+1}$. Каждая из следующих $q$ строк содержит один запрос, состоящий из двух целых значений $i$ и $j(1\le i\le j\le n)$ — границы индексов запроса.

За последним тестом следует строка, содержащая один $0$.

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

Для каждого запроса выведите одно целое число: количество вхождений чаще всего встречаемого числа в заданном интервале.

Примеры