#include <bits/stdc++.h>

using namespace std;

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

int n, q;

struct arbore{

    long long l, r, m, s;


};

arbore arb[300005];
vector <arbore> v;

void Update(int nod, int left, int right, int pos, int x)
{
    if(left == right)
    {
        arb[nod].l = x;
        arb[nod].r = x;
        arb[nod].m = x;
        arb[nod].s = x;
        return;
    }

    int mid = (left+right)/2;

    if(pos <= mid) Update(2*nod, left, mid, pos, x);
    else Update(2*nod+1, mid+1, right, pos, x);

    arb[nod].l = max(arb[2*nod].l, arb[2*nod].s+arb[2*nod+1].l);
    arb[nod].r = max(arb[2*nod+1].r, arb[2*nod+1].s+arb[2*nod].r);
    arb[nod].s = arb[2*nod].s+arb[2*nod+1].s;
    arb[nod].m = max(arb[2*nod].m, max(arb[2*nod+1].m, max(arb[nod].l, max(arb[nod].r, max(arb[nod].s, arb[2*nod].r+arb[2*nod+1].l)))));


}

void Query(int nod, int l1, int r1, int l2, int r2)
{
    if(l1 >= l2 && r2 >= r1)
    {
        v.push_back(arb[nod]);
        return;
    }
    int mid = (l1+r1)/2;

    if(l2 <= mid) Query(2*nod, l1, mid, l2, r2);
    if(mid < r2) Query(2*nod+1, mid+1, r1, l2, r2);


}

int main()
{

    fin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        int x;
        fin >> x;
        Update(1, 1, n, i, x);

    }

    while(q--)
    {
        int a, b;
        fin >> a >>b;
        v.clear();
        Query(1, 1, n, a, b);

        if(v.size() == 1)
            fout << v[0].m << '\n';
        else
        {
            for(int i = 0; i < v.size()-1; i++)
            {
                long long x, y, z, p;
                x = max(v[i].l, v[i].s+v[i+1].l);
                y = max(v[i+1].r, v[i+1].s+v[i].r);
                z = v[i].s+v[i+1].s;
                p = max(v[i].m, max(v[i+1].m, max(x, max(y, max(z, v[i].r+v[i+1].l)))));
                v[i+1].l = x;
                v[i+1].r = y;
                v[i+1].s = z;
                v[i+1].m = p;
            }
            fout << v[v.size()-1].m << '\n';

        }
    }
    return 0;
}