#include<fstream>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<climits>
#include<iomanip>
#include<cstring>
#include<bitset>

#define DIM 100000

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

//ifstream f("in.in");
//ofstream g("out.out");

struct info{
    long long ssmax;
    long long ssst;
    long long ssdr;
    long long sum;
}aint[5*DIM];

long long n,m,sol,a,b,x;

info createInfo(info a,info b){

    info newInfo;

    newInfo.ssmax = max(max(a.ssmax,b.ssmax),a.ssdr+b.ssst);
    newInfo.ssst = max(a.ssst,a.sum+b.ssst);
    newInfo.ssdr = max(b.ssdr,a.ssdr+b.sum);
    newInfo.sum = a.sum+b.sum;

    return newInfo;
}

void build(long long nod,long long st,long long dr){
    if(st == dr){
        f>>x;
        aint[nod].ssmax = x;
        aint[nod].ssst = x;
        aint[nod].ssdr = x;
        aint[nod].sum = x;
    }else{

        long long mid = (st+dr)/2;

        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);

        aint[nod] = createInfo(aint[2*nod],aint[2*nod+1]);
    }
}

info query(long long nod,long long st,long long dr,long long a,long long b){
    if(a<=st && dr<=b){
        return aint[nod];
    }else{

        long long mid = (st+dr)/2;

        info x,y;

        if(a<=mid){
            x=query(2*nod,st,mid,a,b);
        }
        if(mid+1<=b){
            y=query(2*nod+1,mid+1,dr,a,b);
        }
        if(a<=mid && mid+1<=b){
            return createInfo(x,y);
        }else{
            if(a<=mid){
                return x;
            }else{
                return y;
            }
        }
    }
}

signed main(){

    f>>n>>m;
    build(1,1,n);

    for(long long i=1;i<=m;i++){
        f>>a>>b;
        g<<query(1,1,n,a,b).ssmax<<'\n';
    }

    f.close();
    g.close();
    return 0;
}