题目描述

现有一个长度为 $n$ 的序列 $a$，给定你 $m$ 组查询，每次查询序列 $a$ 中从第 $l$ 个数到第 $r$ 个数的最大子段和。

最大子段和：指的是序列 $a$ 中连续的一段子序列的和的最大值。

输入格式

第一行两个整数 $n$，$m$，表示序列长度和查询次数。

第二行 $n$ 个整数 $a_i$，表示序列 $a$。

接下来 $m$ 行，每行两个整数 $l$，$r$，表示查询的范围。

$(1\le n\le 2000,1\le m\le 2\times 10^5,-1000\le a_i\le 1000,1\le l\le r\le n)$

输出格式

输出 $m$ 行，每行一个整数，表示对应查询的最大子段和。

样例输入

8 4
1 4 -3 8 -9 2 -2 1
1 5
2 8
3 6
3 3

样例输出

10
9
8
-3