#include <bits/stdc++.h>

using namespace std;

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

typedef long long i64;

struct nod
{
    i64 ssm,pref,suf,sum;
};

nod aint[400005];
i64 n,m,sp[100005],ans,sufact;
vector<int>composing;

void initialize(int st,int dr,int p)
{
    int fs = 2 * p,fd = 2 * p + 1;
    if (st != dr)
    {
        initialize((st + dr) / 2 + 1,dr,fd);
        initialize(st,(st + dr) / 2,fs);
        aint[p].sum = sp[dr] - sp[st - 1];
        aint[p].pref = max(aint[fs].pref,aint[fs].sum + aint[fd].pref);
        aint[p].suf = max(aint[fd].suf,aint[fd].sum + aint[fs].suf);
        aint[p].ssm = max(aint[fs].suf + aint[fd].pref,max(aint[fd].ssm,aint[fs].ssm));
    }
    else
        aint[p].ssm = aint[p].pref = aint[p].suf = aint[p].sum = sp[st] - sp[st - 1];
}

void query(int st,int dr,int p,int x,int y)
{
    if (st >= x and dr <= y)
    {
        ans = max(ans,aint[p].ssm);
        ans = max(ans,aint[p].pref + sufact);
        sufact = max(aint[p].suf,sufact + aint[p].sum);
    }
    else
    {
        int fs = 2 * p,fd = 2 * p + 1,mid = (st + dr) / 2;
        if (x <= mid)
            query(st,mid,fs,x,y);
        if (y > mid)
            query(mid + 1,dr,fd,x,y);
    }
}

int main()
{
    in >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int x;
        in >> x;
        sp[i] = x + sp[i - 1];
    }
    initialize(1,n,1);
    //for (int i = 1; i < 2 * n; i++)
      //  cout << aint[i].pref << " " << aint[i].suf << " " << aint[i].ssm << " " << aint[i].sum << '\n';
    for (int i = 1; i <= m; i++)
    {
        int x,y;
        ans = -1e14;
        sufact = 0;
        in >> x >> y;
        query(1,n,1,x,y);
        out << ans << '\n';
    }
    return 0;
}