P5012 水の数列

${\rm CYJian}$想到了一个很好玩的游戏呢...

${\rm CYJian}$现在给你一个长度为$N$的数列，你可以选择一个数$x$，然后获得一个得分，得分越大越好。 得分是这样计算的: 首先把小于等于$x$的数标记，然后你的得分就是每一个连续标记的区间的长度的平方和。 ${\rm CYJian}$觉得这样太简单了，~~答案显然就是最大值嘛~~所以他就把得分改成了原来的得分除以你选择的数。 ${\rm CYJian}$还是觉得这样太简单了，所以他需要你选择的数得到的区间的个数在$l$~$r$的范围内。 ${\rm CYJian}$还是觉得这样太简单了，所以他加上了$T$组询问。 ${\rm CYJian}$还是觉得这样太简单了，所以他决定强制在线。

无

无

${\rm Subtask\ 1(30\ pts)}:\qquad 1 \leq N,T \leq 10^2$ ${\rm Subtask\ 2(30\ pts)}:\qquad 1 \leq N,T \leq 10^3$ ${\rm Subtask\ 3(40\ pts)}:\qquad 1 \leq N \leq 10^6 \qquad 1 \leq T \leq 10^3$ $1 \leq Num_i \leq 10^6$ 其余输入的数字均在${\rm int}$范围内。