Задана послідовність 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.
Для кожного запиту виведіть одне ціле число: кількість входжень в заданому інтервалі числа, що найчастіше зустрічається.