#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

const long long INF = 1e12 + 5;
int n, m;
int v[100001];

struct vec
{
    long long sum;
    long long dr;
    long long st;
    long long rez;
}aint[400066];

inline void compute(vec &a, vec b, vec c)
{
    a.sum = b.sum + c.sum;
    a.st = max(b.st, b.sum + c.st);
    a.dr = max(c.dr, c.sum + b.dr);
    a.rez = max(b.dr + c.st, max(b.rez, c.rez));
}

inline void update(int nod, int x, int y, int poz, int val)
{
    if (x == y)
    {
        aint[nod] = {val, val, val, val};
        return;
    }
    int mid = (x + y) / 2;
    if (poz <= mid)
        update(2 * nod, x, mid, poz, val);
    else
        update(2 * nod + 1, mid + 1, y, poz, val);
    compute(aint[nod], aint[2 * nod], aint[2 * nod + 1]);
}

inline vec query(int nod, int x, int y, int start, int finish)
{
    if (start <= x && y <= finish)
        return aint[nod];
    int mid = (x + y) / 2;
    vec a1 = {0, -INF, -INF, -INF};
    vec a2 = {0, -INF, -INF, -INF};
    vec aux = {0, -INF, -INF, -INF};
    if (start <= mid)
        a1 = query(2 * nod, x, mid, start, finish);
    if (mid < finish)
        a2 = query(2 * nod + 1, mid + 1, y, start, finish);
    compute(aux, a1, a2);
    return aux;
}

int main()
{
    int x, y;
    in >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        in >> x;
        update(1, 1, n, i, x);
    }
    for (int i = 1; i <= m; ++i)
    {
        in >> x >> y;
        out << query(1, 1, n, x, y).rez << '\n';
    }
    return 0;
}