Description

你有一个长度为 $n$ 的整数序列 $A$。你需要支持以下询问 :

查询 $[l,r]$ 中满足 $l≤l_1≤r_1≤r$ 的最大的 $f(l_1,r_1)$ 的值。其中 $f(l_1,r_1)=|\sum\limits_{i=l_1}^{r_1} A_i|$。

Format

Input

第一行两个自然数 $n,m$ 。

接下来一行 $n$ 个整数，表示序列的初始值。

接下来 $m$ 行，每行两个自然数，描述了一个查询。

本题的读入/输出量较大，请使用较快的读入/输出方式！

Output

对于每个询问，输出一行一个自然数，表示答案。

Samples

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

2
5
4

三问选择的区间分别是 $[2,2],[2,3],[4,4]$ 。

更多样例

见下发文件

Limitation

本题因为文件大小限制，采用 Subtask 形式评测。

$\text{subtask1(10pts)}:n,m\le50$ 。

$\text{subtask2(10pts)}:n,m\le500$ 。

$\text{subtask3(20pts)}:n,m\le5000$ 。

$\text{subtask4(30pts)}:n,m\le10^5$ 。

$\text{subtask5(30pts)}:n \le 2\times 10^5,m \le 3\times 10^6$ 。

对于 $100\%$ 的数据 $n≤2×10^5,m≤3×10^6,|A_i|≤10^9$。

快读板子

下面的快读板子来自 dysyn1314 ，关注 dysyn1314 ，顿顿解馋！

用法：把这段代码复制到你的代码前面，然后用cin/cout正常写，就会变成快读、快输了。

/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
    if (S == T) {
        T = (S = buf) + fread(buf, 1, SIZE, stdin);
        if (S == T) return '\n';
    }
    return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
    fwrite(buf, 1, S - buf, stdout);
    S = buf;
}
inline void putchar(char c) {
    *S++ = c;
    if (S == T) flush();
}
struct NTR {
    ~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
    template<typename T>
    Reader& operator >> (T& x) {
        char c = getchar();
        T f = 1;
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        x = 0;
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = getchar();
        }
        x *= f;
        return *this;
    }
    Reader& operator >> (char& c) {
        c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        return *this;
    }
    Reader& operator >> (char* str) {
        int len = 0;
        char c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
            str[len++] = c;
            c = getchar();
        }
        str[len] = '\0';
        return *this;
    }
    Reader(){}
} cin;
const char endl = '\n';
struct Writer {
    template<typename T>
    Writer& operator << (T x) {
        if (x == 0) { putchar('0'); return *this; }
        if (x < 0) { putchar('-'); x = -x; }
        static int sta[45];
        int top = 0;
        while (x) { sta[++top] = x % 10; x /= 10; }
        while (top) { putchar(sta[top] + '0'); --top; }
        return *this;
    }
    Writer& operator << (char c) {
        putchar(c);
        return *this;
    }
    Writer& operator << (char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer& operator << (const char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end