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

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

   Вхідні дані

   Складається з декількох тестів. Кожний тест починається з рядка, що містить два цілі числа n та q (1 ≤ n, q ≤ 500000). Наступний рядок містить n цілих чисел a1, ... , an (-500000 ≤ ai ≤ 500000, для кожного 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