Часті значення

Задана послідовність $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$.

Вихідні дані

Для кожного запиту виведіть одне ціле число: кількість входжень в заданому інтервалі числа, що найчастіше зустрічається.

Приклади