#include <bits/stdc++.h>
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int NMAX=1e5;

int n, m;

struct Node{
    int sum;
    int prefmax;
    int sufmax;
    int smax;
    int maxval;
} a[NMAX*4+1];

Node merge(Node L, Node R){
    Node T;
    T.maxval=max(L.maxval, R.maxval);
    T.sum=L.sum+R.sum;
    T.prefmax=max(L.prefmax, L.sum+R.prefmax);
    T.sufmax=max(R.sufmax, R.sum+L.sufmax);
    T.smax=max(max(L.smax, R.smax), L.sufmax+R.prefmax);
    return T;
}

void update(int pos, int val, int  node=1, int st=1, int dr=n){
    if(st==dr){
        a[node]={val, val, val, val, val};
        //if(val>0) a[node]={val, val, val, val, val};
        //else a[node]={val, 0, 0, 0, val};
        return;
    }

    int mid=(st+dr)/2;
    if(pos<=mid){
        update(pos, val, node*2, st, mid);
    }else{
        update(pos, val, node*2+1, mid+1, dr);
    }

    a[node]=merge(a[node*2], a[node*2+1]);
}

Node query(int x, int y, int node=1, int st=1, int dr=n){
    if(x>dr || y<st){
        return {0, 0, 0, 0, INT_MIN};
    }
    if(x<=st && y>=dr){
        return a[node];
    }

    int mid=(st+dr)/2;
    Node Q_st=query(x, y, node*2, st, mid);
    Node Q_dr=query(x, y, node*2+1, mid+1, dr);

    return merge(Q_st, Q_dr);

}

int main(){
    fin >> n >> m;
    for(int i=1; i<=n; i++){
        int x;
        fin >> x;
        update(i, x);
    }
    while(m--){
        int x, y;
        fin >> x >> y;
        Node ans=query(x, y);
        if(ans.smax==0) fout << ans.maxval << '\n';
        else fout << ans.smax << '\n';
    }
}