题目内容

小塔有一个长度为 $n$ 的数组 $a_1, a_2,...,a_n$，他每次会询问一个区间$[l,r]$，他想知道数组$a$的所有长度大于等于$l$且小于等于$r$的子数组之和的最大值是多少。

如果数组$a$可以通过从数组$b$的开头删除若干(可能为零或全部)元素以及从结尾删除若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子数组。

输入描述

第一行输入两个整数$n$和$q(1 ≤ n ≤3000;1≤ q ≤ 10^6)$代表数组中的元素数量和询问次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^9 ≤ a_i ≤ 10^9)$代表数组元素。

此后$q$行，每行输入两个整数$l,r(1 ≤ l ≤ r ≤ n)$代表询问的长度区间。

输出描述

对于每个询问，在一行上输出一个整数代表答案。

补充说明

本题读入量较大，python 代码可以使用

import sys

input = sys.stdin.readline

来加速输入。

样例1

输入

3 2
1 2 -1
1 2
3 3

输出

3
2

说明

对于第一个询问，长度为$1$的子数组有:{$1$}、{$2$}和{$-1$};

长度为$2$的子数组有:{$1,2$}、{$2,-1$}，这五个数组和的最大值为 $max${$1,2,-1,1+2,2-1$}$=3$。

示例2

输入

5 3
1 2 3 4 5
1 1
1 2
1 3

输出

5
9
12

说明