e-olymp
Соревнования

December 18 - RMQ

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

Задана последовательность n целых чисел a1, a2, ... , an в неубывающем порядке. Вам также заданы несколько запросов, состоящих из индексов i и j (1ijn). Для каждого запроса определите число, которое чаще всего встречается среди ai, ... , aj.

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

Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа n и q (1n, q5 ×105). Следующая строка содержит n целых чисел a1, ... , an (-5 ×105ai5 × 105, для каждого i ∈ {1, ... , n}), разделенных пробелом. Считайте, что для каждого i  {1, ..., n - 1}: aiai+1. Каждая из следующих q строк содержит один запрос, состоящий из двух целых значений i и j (1ijn) — границы индексов запроса.

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

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

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

Лимит времени 2 секунды
Лимит использования памяти 128 MiB
Входные данные #1
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Выходные данные #1
1
4
3
Автор Михаил Медведев