#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll


ifstream fin("sequencequery.in"); ofstream fout("sequencequery.out");
#define cin fin
#define cout fout

int n, m;
int p[100010], a[100010];

struct node{
int l, r, mx;
};
node seg[400010];

int rmq1[100010][18], //maximuri
rmq2[100010][18]; //minimuri
int power[100010];

void build_rmq1(){
    for(int i=1; (1ll<<i)<=n; i++){
        for(int j=0; (j+(1ll<<i)-1)<=n; j++){
            rmq1[j][i]=max(rmq1[j][i-1], rmq1[j+(1ll<<(i-1))][i-1]);
        }
    }
}

void build_rmq2(){
    for(int i=1; (1ll<<i)<=n; i++){
        for(int j=0; (j+(1ll<<i)-1)<=n; j++){
            rmq2[j][i]=min(rmq2[j][i-1], rmq2[j+(1ll<<(i-1))][i-1]);
        }
    }
}

void build_power(){
int lg=0;
for(int i=1; i<=(n+1); i++){
    if( (1ll<<(lg+1) )<=i){lg++;}
    power[i]=lg;
}
}


int get_min(int x, int y){
int lg=power[y-x+1];
return min(rmq2[x][lg], rmq2[y-(1ll<<lg)+1][lg]);
}

int get_max(int x, int y){
int lg=power[y-x+1];
return max(rmq1[x][lg], rmq1[y-(1ll<<lg)+1][lg]);
}


void build_seg(int nod, int tl, int tr){
int med=(tl+tr)/2;
if(tl==tr){
    seg[nod].l=a[med]; seg[nod].r=a[med]; seg[nod].mx=a[med]; return;
}
build_seg(nod*2, tl, med); build_seg(2*nod+1, med+1, tr);
seg[nod].l=get_max(tl, tr)-p[tl-1];
seg[nod].r=p[tr]-get_min(tl-1,tr-1);
seg[nod].mx=max(max(seg[2*nod].r+seg[2*nod+1].l, max(seg[2*nod].mx, seg[2*nod+1].mx) ), max(seg[nod].r, seg[nod].l) );
//cout<<seg[nod].l<<" "<<seg[nod].mx<<" "<<seg[nod].r<<" || "<<tl<<" "<<tr<<"\n";
}


int err=1e11;
node query(int nod, int tl, int tr, int x, int y){
node res;
if( (tl>y) || (tr<x) ){
    res.mx=err; return res;
}

int med=(tl+tr)/2;
if( (tl==x) && (tr==y) ){
    res.mx=seg[nod].mx; res.l=seg[nod].l; res.r=seg[nod].r;return res;
}
node res1=query(nod*2, tl, med, x, min(y, med)), res2=query(2*nod+1, (med+1), tr, max(x, (med+1)), y );

res.l=get_max(x, y)-p[x-1];
res.r=p[y]-get_min(x-1, y-1);
if(res1.mx==err){
    res.mx=max(max(res.l, res.r), res2.mx);
}
else{
    if(res2.mx==err){
        res.mx=max(max(res.l, res.r), res1.mx);
    }
    else{
        res.mx=max(max(res.l, res.r), max( max(res1.mx, res2.mx), res1.r+res2.l) );
    }
}
//cout<<res.l<<" "<<res.mx<<" "<<res.r<<" x||x "<<x<<" "<<y<<"\n";
return res;
}



int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=n; i++){cin>>a[i]; p[i]=p[i-1]+a[i]; rmq1[i][0]=p[i]; rmq2[i][0]=p[i]; }
build_rmq1();
build_rmq2();
build_power();
build_seg(1, 1, n);

while(m--){
    int x, y; cin>>x>>y;
    cout<<(query(1, 1, n, x, y).mx)<<"\n";
}



return 0;
}