You are given a sequence of \textbf{n} integers \textbf{a_1 }, \textbf{a_2}, ... , \textbf{a_n} in non-decreasing order. In addition to that, you are given several queries consisting of indices \textbf{i} and \textbf{j} (\textbf{1} ≤ \textbf{i} ≤ \textbf{j} ≤ \textbf{n}). For each query, determine the most frequent value among the integers \textbf{a_i} , ... , \textbf{a_j}. \InputFile Consists of several test cases. Each test case starts with a line containing two integers \textbf{n} and \textbf{q} (\textbf{1} ≤ \textbf{n}, \textbf{q} ≤ \textbf{500000}). The next line contains n integers \textbf{a_1} , ... , \textbf{a_n} (\textbf{-500000} ≤ \textbf{a_i} ≤ \textbf{500000}, for each \textbf{i} ∈ \{\textbf{1}, ..., \textbf{n}\}) separated by spaces. You can assume that for each \textbf{i} ∈ \{\textbf{1}, ..., \textbf{n} - \textbf{1}\}: \textbf{a_i} ≤ \textbf{a_i}_\{+1\}. The following q lines contain one query each, consisting of two integers \textbf{i} and \textbf{j} (\textbf{1} ≤ \textbf{i} ≤ \textbf{j} ≤ \textbf{n}), which indicate the boundary indices for the query. The last test case is followed by a line containing a single \textbf{0}. \OutputFile For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.