#include<bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 5;
const long long INF = 1e18 + 7;
int n, q, v[NMAX];

struct arb
{
    long long ssm, st, dr, sum;
} arbint[4 * NMAX];

arb merge(arb a, arb b)
{
    arb c = {-INF, -INF, -INF, -INF};
    c.sum = a.sum + b.sum;
    c.st = max(a.st, a.sum + b.st);
    c.dr = max(b.dr, a.dr + b.sum);
    c.ssm = max(a.ssm, max(b.ssm, a.dr + b.st));

    return c;
}

void update(int poz, int val, int arbst, int arbdr, int idx)
{
    if(arbst == arbdr)
    {
        arbint[idx] = {val, val, val, val};
        return;
    }

    int mij = (arbst + arbdr) / 2;
    if(poz <= mij)
        update(poz, val, arbst, mij, idx * 2);
    else
        update(poz, val, mij + 1, arbdr, idx * 2 + 1);
    
    arbint[idx] = merge(arbint[idx * 2], arbint[idx * 2 + 1]);
}

arb sol;

void query(int l, int d, int arbst, int arbdr, int idx)
{
    if(arbst > d || arbdr < l)
        return;
    if(arbst >= l && arbdr <= d)
    {
        sol = merge(sol, arbint[idx]);
        return;
    }
    
    int mij = (arbst + arbdr) / 2;
    query(l, d, arbst, mij, idx * 2); 
    query(l, d, mij + 1, arbdr, idx * 2 + 1);
    return;
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    cin >> n >> q;
    for(int i = 1; i <= 4 * n; i++)
        arbint[i] = {-INF, -INF, -INF, -INF};
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i];
        update(i, v[i], 1, n, 1);
    }
    int a, b;
    for(int i = 1; i <= q; i++)
    {
        sol = {-INF, -INF, -INF, -INF};
        cin >> a >> b;
        query(a, b, 1, n, 1);
        cout << sol.ssm << "\n";
    }
}