e-olymp
Змагання

December 18 - RMQ

Часті значення - 2

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

Вхідні дані

Складається з декількох тестів. Кожний тест починається з рядка, що містить два цілі числа n та q (1n, q500000). Наступний рядок містить n цілих чисел a1, ... , an (-500000ai500000, для кожного i ∈ {1, ..., n}), розділених пропуском. Вважайте, що для кожного i ∈ {1, ..., n - 1}: aiai+1. Кожний з наступних q рядків містить один запит, який складається з двох цілих значень i та j (1 i jn) - границі індексів запиту.

За останнім тестом йде рядок, що містить єдиний 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
Автор Михайло Мєдвєдєв