#include <stdio.h>
#include <climits>
using namespace std;
FILE *fin = fopen("sequencequery.in", "r");
FILE *fout = fopen("sequencequery.out", "w");
long long val;
int poz;
int start, finish;
long long curent;
long long rezultat;
struct arbore
{
    long long all, beg, mid, fin;
};
arbore sec[400000];
long long maxim(long long x, long long y)
{
    if(x > y) return x;
    return y;
}
void update(int nod, int st, int dr)
{
    if(st == dr)
    {
        sec[nod].all = val;
        sec[nod].beg = val;
        sec[nod].fin = val;
        sec[nod].mid = val;
        return;
    }
    else
    {
        int mij = (st + dr)/2;
        if(poz <= mij) update(2*nod, st, mij);
        else update(2*nod+1, mij+1, dr);
        sec[nod].all = sec[2*nod].all + sec[2*nod+1].all;
        sec[nod].beg = maxim(maxim(sec[2*nod].beg , sec[2*nod].all+sec[2*nod+1].beg),sec[2*nod+1].all+sec[2*nod].all);
        sec[nod].mid = maxim(maxim(maxim(sec[2*nod].mid , sec[2*nod+1].mid), sec[2*nod].fin+sec[2*nod+1].beg),sec[2*nod+1].all+sec[2*nod].all);
        sec[nod].fin=maxim(maxim(sec[2*nod+1].fin , sec[2*nod+1].all+sec[2*nod].fin), sec[2*nod+1].all+sec[2*nod].all);
    }
}
void intrebare(int nod, int st, int dr)
{
    if(start<=st && finish>=dr)
    {
        rezultat = maxim( rezultat, maxim( curent + sec[nod].beg, sec[nod].mid ) ) ;
        curent = maxim ( curent + sec[nod].all, sec[nod].fin ) ;
        return;
    }
    int mij = st + dr;
    mij /= 2;
    if (start <= mij) intrebare(2*nod, st, mij);
    if (mij < finish) intrebare(2*nod+1, mij+1, dr);
}
int main()
{
    int n,q;
    fscanf(fin, "%d%d", &n, &q);
    for(int i=1;i<=n;i++)
    {
        poz = i;
        fscanf(fin, "%lld", &val);
        update(1,1,n);
    }
    for(int j=1;j<=q;j++)
    {
        int a, b;
        fscanf(fin , "%d%d", &a, &b);
        curent = 0;
        rezultat = LLONG_MIN;
        start = a;
        finish = b;
        intrebare(1,1,n);
        fprintf(fout,  "%lld\n", rezultat);
    }
    return 0;
}