Problem Description

Given a sequence $a$ of length $n$ with indices from $1$ to $n$, there are $m$ queries. Each query gives an interval $[l,r]$. You need to find a sub-interval $[l',r']$ satisfying $l\le l'\le r'\le r$, such that the number of distinct values that appear in $[l',r']$ is less than the number of distinct values that appear in $[l,r]$, and its length $r'-l'+1$ is as large as possible. If no such sub-interval exists, output $0$.

Input Format

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

The next line contains $n$ integers, which are the elements of the sequence $a$.

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

Output Format

For each query, output one integer per line representing the answer.

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

1
2
3
0

Hint

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

Constraints:

For $20\%$ of the testdata, $n,m\le100$.

For $40\%$ of the testdata, $n,m\le1000$.

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

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

Translated by ChatGPT 5