Longest distinct segment queries

You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Process the following query.

• $l$ $r$: Print the largest size among intervals $[s, e]$ with $l \le s \le e \le r$ that contain only distinct values. The size of interval $[s, e]$ is $e-s+1$.

An interval $[s, e]$ with only distinct values must not contain $i$ and $j$ with $A_i = A_j$ ($s \le i < j \le e$).

The first line contains $N$. ($1 \le N \le 500\,000$)

The second line contains the integer sequence $A_1, A_2, \ldots, A_N$, separated by spaces. ($1 \le A_i \le N$)

The third line contains $Q$. ($1 \le Q \le 500\,000$)

From the fourth line through line $Q+3$, each query is given on its own line. ($1 \le l \le r \le N$)

For each query, print the answer on its own line.