#include <fstream>
#include <climits>
#define all first.first
#define st1 first.second
#define dr1 second.first
#define suma second.second
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
long long n,i,sol,suma1,v[100010],m,a,b;
pair< pair<long long,long long> , pair<long long ,long long> > A[400010];
void build(int nod, int st, int dr){
    if(st==dr){
        A[nod].all=v[st];
        A[nod].st1=v[st];
        A[nod].dr1=v[st];
        A[nod].suma=v[st];
    }else{
        int mid=(st+dr)/2;
        build(nod*2,st,mid);
        build(nod*2+1,mid+1,dr);
        A[nod].all=max(A[nod*2].all,max(A[nod*2+1].all,A[nod*2].dr1+A[nod*2+1].st1));
        A[nod].st1=max(A[nod*2].st1,A[nod*2].suma+A[nod*2+1].st1);
        A[nod].dr1=max(A[nod*2+1].dr1,A[nod*2+1].suma+A[nod*2].dr1);
        A[nod].suma=A[nod*2].suma+A[nod*2+1].suma;
    }
}
void query(int nod, int st, int dr){
    if(a<=st&&dr<=b){
        sol=max(sol,max(A[nod].all,suma1+A[nod].st1));
        suma1=max(suma1+A[nod].suma,A[nod].dr1);
        sol=max(sol,suma1);
    }else{
        int mid=(st+dr)/2;
        if(a<=mid)
            query(nod*2,st,mid);
        if(b>mid)
            query(nod*2+1,mid+1,dr);

    }
}
int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>v[i];
    build(1,1,n);
    for(;m--;){
        fin>>a>>b;
        sol=INT_MIN;
        suma1=INT_MIN;
        query(1,1,n);
        fout<<sol<<"\n";
    }
    return 0;
}