Часті значення - 2
Задано послідовність n цілих чисел a_1, a_2, ..., a_n у неспадному порядку. Вам також задано декілька запитів, що складаються з індексів i та j (1 ≤ i ≤ j ≤ n). Для кожного запиту визначить число, яке найчастіше зустрічається серед a_i , ... , a_j.
Вхідні дані
Складається з декількох тестів. Кожний тест починається з рядка, що містить два цілі числа n та q (1 ≤ n, q ≤ 500000). Наступний рядок містить n цілих чисел a_1, ... , a_{n }(-500000 ≤ a_i ≤ 500000, для кожного i ∈ {1, ..., n}), розділених пропуском. Вважайте, що для кожного i ∈ {1, ..., n - 1}: a_i ≤ a_i_{+1}. Кожний з наступних q рядків містить один запит, який складається з двох цілих значень i та j (1 ≤ i ≤ j ≤ n) - границі індексів запиту.
За останнім тестом йде рядок, що містить єдиний 0.
Вихідні дані
Для кожного запиту виведіть одне ціле число: кількість входжень в заданому інтервалі числа, що найчастіше зустрічається.