Частые значения
Частые значения
Задана последовательность 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 ∈ {1, ..., n - 1}: a_i \le a_{i+1}. Каждая из следующих q строк содержит один запрос, состоящий из двух целых значений i и j~(1 \le i \le j \le n) — границы индексов запроса.
За последним тестом следует строка, содержащая один 0.
Выходные данные
Для каждого запроса выведите одно целое число: количество вхождений чаще всего встречаемого числа в заданном интервале.
Пример
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0
1 4 3