[SXZOI 2024 B] 乐

题目背景

有人看乐子，有人照镜子。

赶紧做题，不然看的就是你！

题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。定义 $f(l, r) = |\sum_{i=l}^r a_i|$。

现在有 $q$ 次查询，每次给定 $l, r$。询问 $\max_{l \leq i \leq j \leq r} f(i, j)$。

输入格式

第一行两个正整数 $n, q$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行两个正整数 $l, r$，表示一组询问。

输出格式

对于每次查询，输出一行一个非负整数，表示答案。

样例 #1

样例输入 #1

3 3
-3 2 -3
1 3
2 3
2 2

样例输出 #1

4
3
2

样例 #2

样例输入 #2

6 1
1 1 -4 5 1 4
1 6

样例输出 #2

10

提示

对于前 $40%$ 的数据，保证 $1 \leq n \leq 5000$。

对于前 $80%$ 的数据，保证 $1 \leq q \leq 2 \times 10^5$。

对于所有数据，保证 $1 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^6, -10^9 \leq a_i \leq 10^9, 1 \leq l \leq r \leq n$。

请注意，本题的时间限制较紧。对于最后 20% 的数据，请三思你自己做法的时间复杂度是否正确。