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 $$ **数据要求强制在线**

无

无

**样例解释** 第一个询问 $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])$