#3489. A simple rmq problem

题目描述

因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。

输入格式

第一行为两个整数N,M。M是询问数，N是序列的长度（N<=100000，M<=200000)

第二行为N个整数，描述这个序列{ai}，其中所有1<=ai<=N

再下面M行，每行两个整数x，y，

询问区间[l,r]由下列规则产生（OIER都知道是怎样的吧>_<)：

l=min(（x+lastans)mod n+1,(y+lastans）mod n+1);

r=max(（x+lastans)mod n+1,(y+lastans）mod n+1);

Lastans表示上一个询问的答案，一开始lastans为0

输出格式

一共M行，每行给出每个询问的答案。

样例

样例输入

10 10  

6 4 9 10 9 10 9 4 10 4   

3 8  

10 1  

3 4  

9 4  

8 1  

7 8  

2 9  

1 1  

7 3  

9 9  

样例输出

4  

10  

10  

0  

0  

10  

0  

4  

0  

4  

数据范围与提示

注意出题人为了方便，input的第二行最后多了个空格。

2015.6.24新加数据一组，2016.7.9放至40S,600M,但未重测