5304 - 第二十四章 双指针和莫队:最远间隔距离

给定一个序列,多次询问一段区间 [l,r],求区间中相同的数的最远间隔距离

序列中两个元素的间隔距离指的是两个元素下标差的绝对值

输入

第一行一个整数 n,表示序列长度。

第二行 n 个整数,描述这个序列。

第三行一个整数 m,表示询问个数。

之后 m 行,每行两个整数 l,r 表示询问区间。

输出

m 行,每行一个整数表示答案。如果区间内不存在两个数相同,则输出 0

样例

输入

8
1 6 2 2 3 3 1 6
5
1 4
2 5
2 8
5 6
1 7

输出

1
1
6
1
6

提示

a_i 表示序列元素。

对于 40\% 的数据,满足 1\leq a_i \leq 4001\leq n,m\leq 60000

对于 100\% 的数据,满足 1\leq n,m\leq 2\cdot 10^51\leq a_i\leq 2\cdot 10^9

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题