Frequent values

You are given a sequence of $n$ integers $a_1,a_2,...,a_n$ in non-decreasing order. In addition to that, you are given several queries consisting of indices $i$ and $j(1\le i\le j\le n)$. For each query, determine the most frequent value among the integers $a_i,...,a_j$.

Input

Consists of several test cases. Each test case starts with a line containing two integers $n$ and $q(1\le n,q\le 10^5)$. The next line contains $n$ integers $a_1,a_2,...,a_n(-10^5\le a_i\le 10^5)$. You can assume that for each $i\in 1,...,n-1:a_i\le a_{i+1}$. The following $q$ lines contain one query each, consisting of two integers $i$ and $j(1\le i\le j\le n)$, which indicate the boundary indices for the query.

The last test case is followed by a line containing a single $0$.

Output

For each query, print one line with one integer: the number of occurrences of the most frequent value within the given range.

Examples