P5906 [Template] Rollback Mo's Algorithm & Mo's Algorithm Without Deletions

This is a template problem.

Given a sequence, you will be asked multiple queries on an interval $[l,r]$. For each query, find the **maximum distance between two equal numbers** within the interval. The **distance** between two elements in the sequence means the **absolute difference of their indices**.

The first line contains an integer $n$, which is the length of the sequence. The second line contains $n$ integers describing the sequence. The third line contains an integer $m$, which is the number of queries. Then follow $m$ lines, each containing two integers $l, r$, representing the query interval.

Output $m$ lines. Each line contains one integer, the answer. If there are no two equal numbers in the interval, output $0$.

Let $a_i$ denote the elements of the sequence. For $40\%$ of the testdata, $1\leq a_i \leq 400$, $1\leq n,m\leq 60000$. For $100\%$ of the testdata, $1\leq n,m\leq 2\cdot 10^5$, $1\leq a_i\leq 2\cdot 10^9$。 Translated by ChatGPT 5