DimensionX

一个序列，多组询问，每次询问给出 $l$ 和 $q$，问：

$$
\sum_{i=l}^{l+q-1}\max_{l\le j\le i}a_j
$$

强制在线。

$1\le n,m\le 5\cdot 10^5$