Задана последовательность $n$ целых чисел $a_1, a_2, ..., a_n$ в неубывающем порядке. Вам также заданы несколько запросов, состоящих из индексов $i$ и $j~(1 \le i \le j \le n)$. Для каждого запроса определите число, которое чаще всего встречается среди $a_i, ..., a_j$. \InputFile Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа $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 ∈ {1, ..., n - 1}: a_i \le a_{i+1}$. Каждая из следующих $q$ строк содержит один запрос, состоящий из двух целых значений $i$ и $j~(1 \le i \le j \le n)$ --- границы индексов запроса. За последним тестом следует строка, содержащая один $0$. \OutputFile Для каждого запроса выведите одно целое число: количество вхождений чаще всего встречаемого числа в заданном интервале.