题目描述

森林夜游结束，大笨龙交来一长卷影像，每帧只拍到一种精灵。聪明兔负责剪片。大笨龙每次在胶片上圈出一段，要求那一段里亮过相的精灵，成片里每种都得露一次脸。

聪明兔只能从圈出的范围中连续剪下一段胶片。她可以裁掉开头、结尾，也可以把整段留下。对每个圈出的范围，请算出成片最少要留多少帧。每次询问都使用原胶片。

输入格式

第一行是正整数 n，表示总帧数。第二行给出 n 个正整数，第 i 个数是第 i 帧中精灵的编号。第三行是正整数 q。接下来 q 行，每行两个整数 l、r，表示第 l 帧到第 r 帧，两端均包含。帧从 1 开始编号。

输出格式

按询问顺序输出 q 行，每行一个正整数，表示包含该段全部精灵种类的最短连续子段的帧数。

样例 1

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

2
3
3

第 2 至第 4 帧依次是 3、2、3。保留第 2、3 帧就能让两种精灵都入镜，一帧则办不到。

样例 2

8
1 2 2 3 2 1 1 1
3
1 8
1 4
6 8

3
4
1

对整卷胶片，保留第 4 至第 6 帧的 3、2、1 即可。对第 1 至第 4 帧，编号 1 和 3 只在两端出现，四帧都要留。

样例 3

输入文件 · 答案文件

样例 4

输入文件 · 答案文件

数据范围

1 ≤ n, q ≤ 2000000，1 ≤ 精灵编号 ≤ n，1 ≤ l ≤ r ≤ n。

共 20 个独立测试点，每点 5 分。