1378: 这是一道回滚莫队模板题
Memory Limit：1024 MB
Time Limit：3.000 S
Judge Style：Text Compare
Creator：
Submit：58
Solved：11
Description
善良的（并不）$autumndream$ 为大家准备了一道回滚莫队模板题！
给定一个序列，多次询问一段区间 $[l,r]$，求区间中相同的数的最远间隔距离。序列中两个元素的间隔距离指的是两个元素下标差的绝对值。
但是 $autumndream$ 觉得出模板题不太好！所以这题强制在线，并且对题面进行了修改，要求你输出具有最远间隔距离的那个数，如果有两个数距离相同，则输出较大的数。如果区间内不存在两个数相同，则输出最大的数。
但是善良的（这是真的）$ShadowDrunk$ 指出不要卡空间，所以大家不用担心空间问题！
$autumndream$ 祝你好运。
给定一个序列，多次询问一段区间 $[l,r]$，求区间中相同的数的最远间隔距离。序列中两个元素的间隔距离指的是两个元素下标差的绝对值。
但是 $autumndream$ 觉得出模板题不太好！所以这题强制在线，并且对题面进行了修改，要求你输出具有最远间隔距离的那个数，如果有两个数距离相同，则输出较大的数。如果区间内不存在两个数相同，则输出最大的数。
但是善良的（这是真的）$ShadowDrunk$ 指出不要卡空间，所以大家不用担心空间问题！
$autumndream$ 祝你好运。
Input
第一行一个整数 $n$ ，表示序列长度。
第二行 $n$ 个整数，描述这个序列。
第三行一个整数 $m$ ，表示询问个数。
之后 $m$ 行，每行两个整数 $l$, $r$ 表示询问区间。输入是加密的，解密方法如下：
令上次询问的结果为 $x$（如果这是第一次询问，则 $x = 0$），设 $l=((l_0+x-1)\bmod n) + 1,r=((r_0+x-1) \bmod n) + 1$。如果 $l > r$，则交换 $l, r$。
最终的询问区间为计算后的 $[l, r]$。
保证 $1\le n \le 200000$，$1\le m \le 200000$，$1\le a_i \le 2·10^9$，$1 \leq l_0, r_0 \leq n$。
Output
共 $m$ 行，每行一个整数表示答案。
Sample Input Copy
8
1 6 2 2 3 3 1 6
5
1 4
2 5
2 8
5 6
1 7Sample Output Copy
2
3
2
6
3