#include <fstream>
#define smax first.first
#define sst first.second
#define sdr second.first
#define sum second.second

using namespace std;

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

int n,m,i,x,y,ok;
long long solsmax,solst,soldr,solsum;
pair < pair< long long, long long> , pair < long long, long long> > a[400005];

void build(int nod, int st, int dr)
{
    if (st == dr)
    {
        fin >> a[nod].smax;
        a[nod].sst = a[nod].smax;
        a[nod].sdr = a[nod].smax;
        a[nod].sum = a[nod].smax;
    }
    else
    {
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        a[nod].sum = a[2*nod].sum+a[2*nod+1].sum;
        a[nod].smax = max(a[2*nod].smax, max(a[2*nod+1].smax, a[2*nod].sdr+a[2*nod+1].sst));
        a[nod].sst = max(a[2*nod].sst, a[2*nod+1].sst+a[2*nod].sum);
        a[nod].sdr = max(a[2*nod+1].sdr, a[2*nod].sdr+a[2*nod+1].sum);
    }
}
void query(int nod, int st, int dr, int x, int y)
{
    if (x <= st && dr <= y)
        if (ok == 0)
        {
            solsmax = a[nod].smax;
            solst = a[nod].sst;
            soldr = a[nod].sdr;
            solsum = a[nod].sum;
            ok = 1;
        }
        else
        {
            solsmax = max(solsmax, max(a[nod].smax, soldr+a[nod].sst));
            solst = max(solst, solst+a[nod].sum);
            soldr = max(a[nod].sdr, a[nod].sum+soldr);
            solsum += a[nod].sum;
        }
    else
    {
        int mid = (st+dr)/2;
        if (x <= mid)
            query(2*nod, st, mid, x, y);
        if (y > mid)
            query(2*nod+1, mid+1, dr, x, y);
    }
}

int main()
{
    fin >> n >> m;
    build(1, 1, n);
    for (i=1; i<=m; i++)
    {
        fin >> x >> y;
        solsmax = 0;
        solst = 0;
        soldr = 0;
        solsum = 0;
        ok = 0;
        query(1, 1, n, x, y);
        fout << solsmax << "\n";
    }
    return 0;
}