P7907 [Ynoi2005] rmscne

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$.

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 $q$ lines, each containing one positive integer representing the answer.

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