#P3489. A simple rmq problem

A simple rmq problem

A simple RMQ problem

题目描述

给定序列 a1,…,ana_1,\ldots,a_n。每次询问给出一个闭区间 [l,r][l,r]。找出在 al,…,ara_l,\ldots,a_r 中恰好出现一次的最大数。如果不存在这样的数,答案为 00。

询问必须按输入顺序解码和回答。

输入格式

第一行包含两个整数 n,mn,m,分别表示序列的长度和询问数。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

之后 mm 行,每行包含两个整数 x,yx,y。设 lastans\mathrm{lastans} 为上一问的答案,第一问之前取 00。先计算

$$u=((x+\mathrm{lastans})\bmod n)+1,\qquad v=((y+\mathrm{lastans})\bmod n)+1,$$

再取 l=min⁡(u,v)l=\min(u,v),r=max⁡(u,v)r=\max(u,v)。

输出格式

每次询问输出一行一个整数,表示该询问的答案。

样例 #1

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

数据范围

n≤105n\le 10^5,m≤2×105m\le 2\times10^5,1≤ai≤n1\le a_i\le n。