题目描述

给定长为 $n$ 的序列，$q$ 次询问区间 $[l,r]$ 的最短子区间 $[l',r']$，满足所有在 $[l,r]$ 中出现的数也在 $[l',r']$ 中出现. 你只需要输出 $[l',r']$ 的长度 $r'-l'+1$。

输入格式

第一行一个正整数 $n$。

接下来一行有 $n$ 个正整数，表示序列的元素。

接下来一行有一个正整数 $q$

接下来 $q$ 行，每行两个正整数 $l,r$ 表示一个询问。

输出格式

$q$ 行，每行一个正整数表示答案。

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

2
3
3

提示

Idea：qwaszx，Solution：qwaszx，Code：qwaszx，Data：qwaszx

对于 $20\%$ 的数据，满足 $n,q,a_i\leq 5\times 10^3$。

对于 $50\%$ 的数据，满足 $n,q,a_i\leq 5\times 10^4$。

对于 $100\%$ 的数据，满足 $1\leq n,q\leq 2\times 10^6$，$1\leq a_i\leq n$。