P9991 [Ynoi Easy Round 2023] TEST_107

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

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

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

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