#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 1<<19
#define lf (2*n)
#define rt (2*n+1)
#define INF 0xfffffff

int n,m,s[MAX],d[MAX],bst[MAX],v[MAX],x,y,l_m, rs;

void build(int n,int l,int r){
    if(l == r)
    {
        scanf("%d",&bst[n]);
        s[n] = d[n] = v[n] = bst[n];
        return ;
    }
        int m = (l+r)/2;
        build(lf,l,m);
        build(rt,m+1,r);
        v[n] = v[lf] + v[rt];
        d[n] = max( d[rt], d[lf] + v[rt] );
        s[n] = max( s[lf], v[lf] + s[rt] );
        bst[n] = max( d[lf] + s[rt] , max( bst[lf], bst[rt] ) );
}

void query(int n,int l,int r){
    if(x <= l && r <= y)
    {
        rs = max(rs, bst[n] );
        rs = max(rs, l_m + s[n] );
        l_m = max( l_m + v[n], d[n] );
        return ;
    }
        int m = (l+r)/2;
        if( x <=m) query(lf,l,m);
        if( y > m)query(rt,m+1,r);
}

int main(){
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    scanf("%d %d",&n,&m);
    build(1,1,n);

   for(int i=1;i<=m;i++)
   {
       scanf("%d %d",&x,&y);
       rs = -INF;
       l_m = 0;
       query(1,1,n);
       printf("%d\n",rs);
   }
    return 0;
}