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