5304 - 第二十四章 双指针和莫队:最远间隔距离
时间限制 : 1 秒
内存限制 : 128 MB
给定一个序列,多次询问一段区间 [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 400,1\leq n,m\leq 60000。
对于 100\% 的数据,满足 1\leq n,m\leq 2\cdot 10^5,1\leq a_i\leq 2\cdot 10^9。