Frequent Values

Source: UVa

Version: Phuoc Hung OJ Extended

You are given a non-decreasing sequence $A_1,A_2,\ldots,A_N$. Each of the $Q$ queries gives two indices $i,j$ with $1\le i\le j\le N$.

For every query, determine the largest frequency of any value among $A_i,A_{i+1},\ldots,A_j$.

The original UVa task contains multiple test cases terminated by a line containing 0. This Phuoc Hung OJ version contains one test case per input file.

Input

The first line contains $N,Q$.

The second line contains the non-decreasing sequence $A_1,\ldots,A_N$.

Each of the next $Q$ lines contains $i,j$.

Output

For every query, print the maximum frequency in the requested range.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$, $-1000\le A_i\le 1000$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $-10^5\le A_i\le 10^5$.
• Subtask 3 — 50%: $1\le N,Q\le 10^5$, $-10^5\le A_i\le 10^5$.

Examples

Input

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

Output

1
4
3

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.