#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");
    int v[100001],n,m, a[2][100001];
    f>>n>>m;
    for(int i=1;i<=n;i++) f>>v[i];
    for(int i=1;i<=m;i++) f>>a[0][i]>>a[1][i];

    int pozi, pozj,maxsum, maxcurent, maxprev,j;
    for(int i=1;i<=m;i++)
    {
        pozi=a[0][i];
        pozj=a[1][i];
        maxprev=v[pozi];maxsum=v[pozi];
        for(j=pozi;j<=pozj;j++)
        {
            maxcurent = max(v[j], maxprev + v[j]);
            if(maxcurent>maxsum) maxsum=maxcurent;
            maxprev=maxcurent;
        }
    g<<maxsum<<endl;
    }
}