P5648 Mivik的神力

$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ 发怒了，机房的 $\textcolor{grey}{\text{deco}}$ 瑟瑟发抖

$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ 要写一篇文章，在写文章时，他有 $n$ 个备选的单词，第 $i$ 个单词有一个长度 $a_i$，$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ 可以选择从第 $i$ 个单词开始写作，一共写 $k$ 秒，第 $j$ 秒会写上第 $i+j-1(j\in[1,k])$ 个单词，并且他在写作时每秒都会获得愉悦值，第 $j$ 秒的愉悦值为 $\max_{l=i}^{i+j-1} a_l$，现在，请你帮他算出，他每一次写作获得的愉悦值之和。 **一句话题意：给出一个序列和多组询问 $(l,q)$ ，求** $$ \sum_{i=l}^{l+q-1} \max_{l\le j\le i}a_j $$ **数据要求强制在线。**

第一行，两个数，$n$，$t$，代表词汇个数和问题个数 第二行，$n$ 个数，第 $i$ 个数代表 $a_i$。 接下来 $t$ 行，每行两个数，$u$，$v$，$l=1+(u \oplus lastans)\bmod n$，$q=1+(v \oplus (lastans+1))\bmod (n-l+1)$，代表查询从第 $l$ 秒开始，写作 $q$ 秒的愉悦度之和 $lastans$ 表示上一次查询的答案，初始 $lastans$ 为 $0$。

对于每个询问，回答一行，代表答案。

**样例解释** 第一个询问 $1,1$，解密后得到 $l=2,q=1$ ，则按题意可得所求即为区间 $[2,2]$ 的最大值，为 $2$。 第一个询问 $1,2$ ，解密后得到 $l=1,q=2$ ，则所求即为区间 $[1,1]$ 和区间 $[1,2]$ 的最大值之和，为 $3$。 ----- 对于 $20\%$ 的数据，$n \leq 1000$，$t \leq 1000$； 对于 $100\%$ 的数据，$n\leq 500000$，$t\leq 500000$，$1 \leq a_i\leq 10^9(i\in [1,n])$。