#include <bits/stdc++.h>

using namespace std;

struct nod{
    int left,right,best,sum;
};

#define N 1000555
nod node[2*N];
int v[N];


void build(int id,int s,int d){
    if( s == d ){
        int x = v[s];
        node[id]={x,x,x,x};
        return;
    }
    int m = (s+d)>>1;
    build(id*2 , s , m );
    build(id*2+1,m+1,d);
    node[id].left  = max( node[id*2].left , node[id*2].sum + node[id*2+1].left );
    node[id].right = max( node[id*2+1].right , node[id*2+1].sum + node[id*2].right );
    node[id].best  = max( node[id*2].right + node[id*2+1].left , max(node[id*2].best , node[id*2+1].best) );
    node[id].sum   = node[id*2].sum + node[id*2+1].sum;

}

int x,y;
long long sum,val;

long long max(long long a , long long b)
{
    if(a>b)return a;
    return b;
}

void query(int id,int s,int d){
    if( x <= s && d <= y  ){
        if( sum < 0 )
            sum = 0;
        val  = max( val , max(node[id].best,sum + node[id].left) );
        sum = max( sum+node[id].sum , node[id].right  );
        return ;
    }

    int m = (s+d)>>1;
    if( x <= m  )
        query(id*2 , s , m );
    if( m < y )
        query(id*2+1,m+1,d);
}


int main()
{
    int n,m;
    freopen("sequencequery.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]);
    build(1,1,n);
    for(int i=1;i<=m;++i){
        scanf("%d %d",&x,&y);

        val = -(1<<28);
        sum = 0;
        query(1,1,n);
        printf("%lld\n",val);
    }



    freopen("sequencequery.out","w",stdout);
    return 0;
}