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