#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],p[MAX],u[MAX],x,y,l_m;
long long v[100001],rs;

void build(int n,int l,int r){
    if(l == r)
    {
        p[n] = r;
        u[n] = r;
        s[n] = r;
        d[n] = r;
        return ;
    }
        int m = (l+r)/2;
        build(lf,l,m);
        build(rt,m+1,r);
        if( v[r] - v[ d[lf] - 1] > v[r] - v[ d[rt] - 1] )d[n] = d[lf]; else d[n] = d[rt];
        if( v[ s[rt] ] - v[l - 1] > v[ s[lf] ] - v[l - 1] )s[n] = s[rt]; else s[n] = s[lf];
        long long s1 = v[ u[lf] ] - v[ p[lf] - 1], s2 = v[ u[rt] ] - v[ p[rt] - 1];
        if( s1 > s2 ){ p[n] = p[lf]; u[n] = u[lf]; } else { s1 = s2; p[n] = p[rt]; u[n] = u[rt]; }
            s2 = v[ s[rt] ] - v[ d[lf] - 1];
        if(s2 > s1 ){ p[n] = d[lf]; u[n] = s[rt]; }
}

void query(int n,int l,int r){
    if(x <= l && r <= y)
    {
        rs = max(rs, v[ u[n] ] - v[ p[n] - 1] );
        rs = max(rs, v[ s[n] ] - v[ l_m - 1] );
        if( v[r] - v[l_m - 1] < v[r] - v[ d[n] - 1 ] )l_m = 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);
    for(int i=1;i<=n;i++)scanf("%lld ",&v[i]);
    for(int i=1;i<=n;i++) v[i] += v[i-1];
    build(1,1,n);

   // printf("%d %d\n",p[1],u[1]);

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

   // for(int i=1;i<=100;i++)
    //if( p[i] )
   // printf("%d ",v[ u[i] ] - v[ p[i] - 1]);

    return 0;
}