Problem Description

Given a sequence of length $n$ and $q$ queries, for each query interval $[l,r]$, find the shortest sub-interval $[l',r']$ such that every number that appears in $[l,r]$ also appears in $[l',r']$. You only need to output the length of $[l',r']$, i.e. $r'-l'+1$.

Input Format

The first line contains one positive integer $n$.

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

The next line contains one positive integer $q$.

The next $q$ lines each contain two positive integers $l,r$, representing a query.

Output Format

Output $q$ lines, each containing one positive integer representing the answer.

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

2
3
3

Hint

Idea: qwaszx, Solution: qwaszx, Code: qwaszx, Data: qwaszx.

For $20\%$ of the testdata, $n,q,a_i\leq 5\times 10^3$.

For $50\%$ of the testdata, $n,q,a_i\leq 5\times 10^4$.

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

Translated by ChatGPT 5