#include <iostream>
#include <fstream>
using namespace std;

struct Nod{
    int pl,pr,s,b;
};

int N,M,a[100010],x,y,bl,ans; Nod tree[500000];

void build(int nod,int l, int r){
    if (l==r){
        tree[nod].pl=tree[nod].pr=tree[nod].s=tree[nod].b=a[l];
        return;
    }

    int mid=(l+r)>>1;
    build(2*nod,l,mid);
    build(2*nod+1,mid+1,r);
    tree[nod].s=tree[nod*2].s+tree[nod*2+1].s;
    tree[nod].pl=max(tree[nod*2].pl,tree[nod*2].s+tree[nod*2+1].pl);
    tree[nod].pr=max(tree[nod*2+1].pr,tree[nod*2+1].s+tree[nod*2].pr);
    tree[nod].b=max(max(tree[nod*2].b,tree[nod*2+1].b),tree[nod*2].pr+tree[nod*2+1].pl);
}


void query(int nod, int l, int r){
    if (x<=l && r<=y){
        bl=max(bl+tree[nod].s,tree[nod].pr);
        ans=max(ans,max(tree[nod].b,bl+tree[nod].pr));
        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;
    for (i=1; i<=N; i++) fin >> a[i];

    build(1,1,N);

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

    return 0;
}