P5648 Mivik's Divine Power

$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ is angry, and $\textcolor{grey}{\text{deco}}$ in the computer lab is trembling with fear.

$\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ wants to write an article. While writing, he has $n$ candidate words. The $i$-th word has length $a_i$. $\textcolor{black}{\text{M}} \textcolor{red}{\text{ivik}}$ can choose to start writing from the $i$-th word and write for a total of $k$ seconds. In the $j$-th second, he writes the $(i+j-1)$-th word $(j\in[1,k])$. While writing, he gains happiness points every second. The happiness points in the $j$-th second are $\max_{l=i}^{i+j-1} a_l$. Now please help him compute, for each writing process, the sum of happiness points he gains. **One-sentence statement: Given a sequence and multiple queries $(l,q)$, compute** $$ \sum_{i=l}^{l+q-1} \max_{l\le j\le i}a_j $$ **The testdata requires mandatory online processing.**

The first line contains two integers $n$ and $t$, representing the number of words and the number of queries. The second line contains $n$ integers. The $i$-th integer represents $a_i$. In the next $t$ lines, each line contains two integers $u$ and $v$, where $l=1+(u \oplus lastans)\bmod n$ and $q=1+(v \oplus (lastans+1))\bmod (n-l+1)$. This represents a query asking for the sum of happiness points when starting from the $l$-th second and writing for $q$ seconds. $lastans$ denotes the answer to the previous query, with initial value $lastans=0$.

For each query, output one line containing the answer.

**Sample Explanation** For the first query $1,1$, after decoding we get $l=2,q=1$. Then according to the statement, the answer is the maximum value on interval $[2,2]$, which is $2$. For the first query $1,2$, after decoding we get $l=1,q=2$. Then the answer is the sum of the maximum values on intervals $[1,1]$ and $[1,2]$, which is $3$. ----- For $20\%$ of the testdata, $n \leq 1000$ and $t \leq 1000$. For $100\%$ of the testdata, $n\leq 500000$, $t\leq 500000$, and $1 \leq a_i\leq 10^9(i\in [1,n])$. Translated by ChatGPT 5