Given a sequence $a$ of length $n$ with indices from $1$ to $n$, there are $m$ queries. Each query provides an interval $[l, r]$. Find a sub-interval $[l', r']$ such that $l \le l' \le r' \le r$, the number of distinct values in $[l', r']$ is strictly less than the number of distinct values in $[l, r]$, and the length $r' - l' + 1$ is maximized. If no such sub-interval exists, output $0$.

Input

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers representing the elements of the sequence $a$.

The next $m$ lines each contain two integers $l$ and $r$ representing a query. You only need to output the length of the sub-interval, i.e., $r' - l' + 1$.

Output

For each query, output a single integer representing the answer on a new line.

Examples

Input 1

5 4
1 3 2 3 4
2 4
1 3
2 5
1 1

Output 1

1
2
3
0

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078

For $20\%$ of the data, $n, m \le 100$.

For $40\%$ of the data, $n, m \le 1000$.

For another $20\%$ of the data, $a_i \le 10$.

For $100\%$ of the data, $1 \le n, m, a_i \le 2 \times 10^6$.