#include <bits/stdc++.h>
using namespace std;
const int Q=1<<20;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
struct nod1
{   long long int maxsum;
    long long int sum;
    long long int prefsum;
    long long int sufsum;
};
long long int n,a,m;
nod1 arb[Q];
void update(int nod,int st,int dr,int index,int value)
{   if (st == dr)
    {   arb[nod].maxsum = arb[nod].prefsum = arb[nod].sufsum = arb[nod].sum = value;
        return ;
    }
    int mid = (st+dr)/2;
    if (index <= mid) update(2*nod,st,mid,index,value);
    else update(2*nod+1,mid+1,dr,index,value);
    arb[nod].sum = arb[2*nod].sum + arb[2*nod+1].sum;
    arb[nod].prefsum = max(arb[2*nod].prefsum, arb[2*nod].sum + arb[2*nod + 1].prefsum);
    arb[nod].sufsum = max(arb[2*nod+1].sufsum, arb[2*nod+1].sum + arb[2*nod].sufsum);
    arb[nod].maxsum = max(arb[2*nod].maxsum, max(arb[2*nod+1].maxsum, arb[2*nod].sufsum + arb[2*nod+1].prefsum));
}
long long int rez,d;
void query(int nod,int st,int dr,int a,int b)
{   if (b < st || a > dr) return ;
    if (a <= st && dr <= b)
    {   if (rez < arb[nod].maxsum) rez = arb[nod].maxsum;
        if (rez < d + arb[nod].prefsum) rez = d + arb[nod].prefsum;
        d = max(d + arb[nod].sum, arb[nod].sufsum);
        if (d > rez) rez = d;
        return ;
    }
    int mid = (st+dr)/2;
    query(2*nod, st,mid,a,b);
    query(2*nod+1,mid+1,dr,a,b);
}
int main()
{   in >> n >> m;
    for (int i=1; i<=n; i++)
    {   in >> a;
        update(1,1,1<<18,i,a);
    }
    for (int a,b,i=1; i<=m; i++)
    {   in >> a >> b;
        rez = -2147483640;
        d = 0;
        query(1,1,1<<18,a,b);
        out << rez << "\n";
    }
    return 0;
}