#include<stdio.h>
#include<algorithm>
using namespace std;
FILE *f,*g;

const int M=300005,N=100005;
int n,m;

struct detoate{
    int mic,mare,best;
}dumm,dumm1,dumm2,ai[M];

int v[N];

void build(int poz,int st,int dr){
    
    if (st==dr){
        
        ai[poz].mic=v[st-1];
        ai[poz].mare=v[st];
        ai[poz].best=v[st]-v[st-1];
    
    }

    else{
        
        int p1=2*poz,p2=2*poz+1,mid=(st+dr)/2;
        build(p1,st,mid);
        build(p2,mid+1,dr);
        ai[poz].mic=min(ai[p1].mic,ai[p2].mic);
        ai[poz].mare=max(ai[p1].mare,ai[p2].mare);
        ai[poz].best=max(ai[p2].mare-ai[p1].mic,ai[p1].best);
        ai[poz].best=max(ai[poz].best,ai[p2].best);

    }
}

detoate query(int poz,int st,int dr,int fi,int la){
    
    if (fi==st&&la==dr) return ai[poz];
    
    else{

        int mid=(st+dr)/2,p1=2*poz,p2=2*poz+1;
        
        if (mid+1<=fi) return query(p2,mid+1,dr,fi,la);
        else if (mid>=la) return query(p1,st,mid,fi,la);
            else{

                dumm1=query(p1,st,mid,fi,mid);
                dumm2=query(p2,mid+1,dr,mid+1,la);
                dumm.mic = min( dumm1.mic, dumm2.mic );
                dumm.mare = max( dumm1.mare, dumm2.mare );
                dumm.best = max( dumm2.mare-dumm1.mic, dumm1.best);
                dumm.best = max ( dumm.best, dumm2.best );
                return dumm;
            }

    }

}


void read(void){
    
    int i,a;

    f=fopen("sequencequery.in","r");
    g=fopen("sequencequery.out","w");
    
    fscanf(f,"%d%d",&n,&m);
    
    v[0]=0;
    for(i=1;i<=n;i++){
        fscanf(f,"%d",&a);
        v[i]=v[i-1]+a;
    }

}

void solve(void){
    
    int i,a,b;
    
    build(1,1,n);

    for(i=1;i<=m;i++){
        fscanf(f,"%d%d",&a,&b);
        fprintf(g,"%d\n",query(1,1,n,a,b).best);
    }

}





int main(void){
    
    read();
    solve();
    return 0;
}