#include <iostream>
#include <fstream>
#define LL long long int
using namespace std;

struct Nod{
    LL maxs,mins,b;
};

LL N,M,sum[100010],ans,x,y,MINS; Nod t[400000];

void build(int nod, int l, int r){
    if (l==r){
        t[nod].maxs=sum[l];
        t[nod].mins=sum[l-1];
        t[nod].b=sum[l]-sum[l-1];
        return;
    }

    int mid=(l+r)>>1;
    build(nod*2,l,mid);
    build(nod*2+1,mid+1,r);
    t[nod].maxs=max(t[nod*2].maxs,t[nod*2+1].maxs);
    t[nod].mins=min(t[nod*2].mins,t[nod*2+1].mins);
    t[nod].b=max(max(t[nod*2].b,t[nod*2+1].b),t[nod*2+1].maxs-t[nod*2].mins);
}

void query(int nod, int l, int r){
    if (x<=l && r<=y){
        ans=max(max(ans,t[nod].b),t[nod].maxs-MINS);
        MINS=min(MINS,t[nod].mins);
        return;
    }

    int mid=(l+r)>>1;
    if (x<=mid) query(nod*2,l,mid);
    if (y>mid)  query(nod*2+1,mid+1,r);
}

int main(){
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    fin >> N >> M;

    int i; LL el;
    for (i=1; i<=N; i++){
        fin >> el;
        sum[i]=sum[i-1]+el;
    }
    build(1,1,N);

    for (i=1; i<=M; i++){
        fin >> x >> y;
        ans=-(1LL<<60);
        MINS=1LL<<60;
        query(1,1,N);
        fout << ans << "\n";
    }
    return 0;
}