#P18743. [正睿NOI2021训练] 第五题

[正睿NOI2021训练] 第五题

第五题

给定长度为 nn 的正整数序列 aa。

有 qq 次询问,每次给出区间 [l,r][l,r]。你需要在该区间内部找到一个最短子区间 [l′,r′][l',r'],使得 [l,r][l,r] 中出现过的每一种数字,都至少在 [l′,r′][l',r'] 中出现一次。

即要求 l≤l′≤r′≤rl\le l'\le r'\le r,且两个区间中出现的不同数字组成的集合相同。只需输出最小长度 r′−l′+1r'-l'+1。

输入格式

第一行一个正整数 nn;第二行 nn 个正整数 a1,…,ana_1,\ldots,a_n。

第三行一个正整数 qq;接下来 qq 行,每行两个整数 l,rl,r。

输出格式

输出 qq 行,每行一个正整数,表示最短子区间长度。

数据范围

1≤n,q≤2×1061\le n,q\le2\times10^6,1≤ai≤n1\le a_i\le n,1≤l≤r≤n1\le l\le r\le n。

样例 1

输入

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

输出

2

3

3