eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

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

Пример

Входные данные #1
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Выходные данные #1
1
4
3