数据结构

给一个长为 $n$ 的序列 $a$，下标为 $1$ 到 $n$，有 $m$ 次查询操作，每次给出一个区间 $[l,r]$，求一个子区间 $[l',r']$，满足 $l\le l'\le r'\le r$，$[l',r']$ 中出现过的值个数比 $[l,r]$ 中出现过的值个数少，且其长度即 $r'-l'+1$ 最大。若 $l'>r'$，则认为没有值在 $[l',r']$ 中出现过。

第一行一个数表示 $n (1 \le n \le 2\times 10^6)$。

之后一行 $n$ 个数依次表示序列 $a(1 \le a_i \le 2\times 10^6)$ 中的元素。

之后一行一个数表示 $m (1 \le m \le 2\times 10^6)$。

之后 $m$ 行，每行两个数 $l,r$ 表示一次查询，只需输出该子区间的长度，即 $r'-l'+1$。

对于每次查询，输出一行一个数表示答案。

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

1
2
3
0

2021 年百度之星·程序设计大赛 - 初赛三