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 ≤ i ≤ j ≤ n)$. For each query, determine the most frequent value among the integers $a_{i}, ... , a_{j}$.

输入格式

The input consists of several test cases. Each test case starts with a line containing two integers $n$ and $q (1 ≤ n, q ≤ 100000)$. The next line contains $n$ integers $a_{1}, ... , a_{n}(-100000 ≤ a_{i} ≤ 100000$ for each $i ∈ \{1, ..., n\})$ separated by spaces. You can assume that for each $i ∈ \{1, ..., n-1\}: a_{i} ≤ a_{i+1}$. The following $q$ lines contain one query each, consisting of two integers $i$ and $j (1 ≤ i ≤ j ≤ n)$, which indicate the boundary indices for the query.

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

输出格式

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

样例 #1

样例输入 #1

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

样例输出 #1

1
4
3