#P18743. [正睿NOI2021训练] 第五题
[正睿NOI2021训练] 第五题
第五题
给定长度为 的正整数序列 。
有 次询问,每次给出区间 。你需要在该区间内部找到一个最短子区间 ,使得 中出现过的每一种数字,都至少在 中出现一次。
即要求 ,且两个区间中出现的不同数字组成的集合相同。只需输出最小长度 。
输入格式
第一行一个正整数 ;第二行 个正整数 。
第三行一个正整数 ;接下来 行,每行两个整数 。
输出格式
输出 行,每行一个正整数,表示最短子区间长度。
数据范围
,,。
样例 1
输入
5
1 3 2 3 4
3
2 4
1 3
2 5
输出
2
3
3