#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100005;
const int INF = -1e9;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
struct arb{
int a,b,s,m;
};
arb A[4 * NMAX];
int V[NMAX],S,Sol;
inline void buildtree(int nod, int l,int r){
    if(l == r){
        A[nod].a = A[nod].b = A[nod].s = A[nod].m = V[l];
        return ;
    }
    int mid = (l + r) / 2;
    buildtree(2 * nod,l,mid);
    buildtree(2 * nod + 1,mid + 1, r);
    A[nod].s = A[2 * nod].s + A[2 * nod + 1].s;
    A[nod].a = max(A[2 * nod].a,A[2 * nod].s + A[2 * nod + 1].a);
    A[nod].b = max(A[2 * nod + 1].b,A[2 * nod + 1].s + A[2 * nod].b);
    A[nod].m = max(max(A[2 * nod].m,A[2  * nod + 1].m), A[2 * nod].b + A[2 * nod + 1].a);

}
inline void query(int nod,int l,int r,int m,int M){
    if(m <= l && M >= r){
        Sol = max(Sol,max(A[nod].m,S + A[nod].a));
        S = max(S + A[nod].s, A[nod].b);
        return;
    }
    int mid = (l + r)/2;
    if(m <= mid)
        query(2 * nod,l,mid,m,M);
    if(mid < M)
        query(2 * nod + 1, mid + 1,r,m,M);

}
int main()
{
    int n,m,l,r;
    fin >> n >> m;;
    for(int i = 1; i <= n; i++){
        fin >> V[i];
    }
    buildtree(1,1,n);
    for(int i = 1; i <= m; i++){
        fin >> l >> r;
        Sol = INF;
        S = 0;
        query(1,1,n,l,r);
        fout << Sol << "\n";
    }
    return 0;
}