[Ynoi2005] rmscne
题目描述
给定长为 $n$ 的序列,$q$ 次询问区间 $[l,r]$ 的最短子区间 $[l',r']$,满足所有在 $[l,r]$ 中出现的数也在 $[l',r']$ 中出现. 你只需要输出 $[l',r']$ 的长度 $r'-l'+1$。
输入输出格式
输入格式
第一行一个正整数 $n$。
接下来一行有 $n$ 个正整数,表示序列的元素。
接下来一行有一个正整数 $q$
接下来 $q$ 行,每行两个正整数 $l,r$ 表示一个询问。
输出格式
$q$ 行,每行一个正整数表示答案。
输入输出样例
输入样例 #1
5
1 3 2 3 4
3
2 4
1 3
2 5
输出样例 #1
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$。