#include <fstream>
using namespace std;

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

int n,m,i,j,a[400001][5],ok,sol,sum;

void build(int nod, int st, int dr){
    if(st==dr){
        fin>>a[nod][1];/// 1-secventa optima din sir st-dr
        a[nod][2]=a[nod][1];/// 2-secventa optima ce contine inceputul
        a[nod][3]=a[nod][1];/// 3-secventa optima ce contine finalul
        a[nod][4]=a[nod][1];/// 4-secventa ce contine suma de la st-dr
    }else{
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        a[nod][1]=max(a[2*nod][1],max(a[2*nod+1][1],a[2*nod][3]+a[2*nod+1][2])); /** final 2*nod + inceput 2*nod+1*/
        a[nod][2]=max(a[2*nod][2],a[2*nod][4]+a[2*nod+1][2]);
        a[nod][3]=max(a[2*nod+1][3],a[2*nod+1][4]+a[2*nod][3]);
        a[nod][4]=a[2*nod][4]+a[2*nod+1][4];
    }
}

void query(int nod, int st, int dr){
    if(st>=i && dr<=j){
        sol=max(a[nod][1],max(sol,sum+a[nod][2]));
        sum=max(sum+a[nod][4],a[nod][3]);
        sol=max(sol,sum);
    }else{
        int mid=(st+dr)/2;
        if(i<=mid)
            query(2*nod,st,mid);
        if(j>mid)
            query(2*nod+1,mid+1,dr);
    }
}

int main(){
    fin>>n>>m;
    build(1,1,n);

    for(;m;m--){
        sum=-1000001;
        sol=-1000001;
        ok=1;

        fin>>i>>j;
        query(1,1,n);
        fout<<max(sol,sum)<<"\n";
    }

    return 0;
}