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

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

struct detoate{
    long long mic,mare,best;
}ai[M];

long long 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= (ai[p1].mic<ai[p2].mic) ? ai[p1].mic : ai[p2].mic;
        ai[poz].mare= (ai[p1].mare>ai[p2].mare) ? 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){
    
    detoate dumm,dumm1,dumm2;

    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);
                if (dumm2.best>dumm.best) 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;
    detoate dumm;
    
    build(1,1,n);

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

}





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

}