Частые значения - 2
Частые значения - 2
Задана последовательность n целых чисел a1
, a2
, ... , an
в неубывающем порядке. Вам также заданы несколько запросов, состоящих из индексов i и j (1 ≤ i ≤ j ≤ n). Для каждого запроса определите число, которое чаще всего встречается среди ai
, ... , aj
.
Входные данные:
Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа n и q (1 ≤ n, q ≤ 5×105
). Следующая строка содержит n целых чисел a1
, ... , an
(-5×105
≤ ai
≤ 5×105
, для каждого i ∈ {1, ... , n}), разделенных пробелом. Считайте, что для каждого i ∈ {1, ..., n - 1}: ai
≤ ai+1
. Каждая из следующих q строк содержит один запрос, состоящий из двух целых значений i и j (1 ≤ i ≤ j ≤ n) — границы индексов запроса.
За последним тестом следует строка, содержащая один 0.
Выходные данные:
Для каждого запроса выведите одно целое число: количество вхождений чаще всего встречаемого числа в заданном интервале.
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0
1 4 3