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