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

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

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