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

struct nod{int left,right,best,sum;}node[2*N];
int v[N];

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


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;

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);
    freopen("sequencequery.out","w",stdout);
    for(int i = 1;i <= m; ++i)
    {
        scanf("%d %d",&x,&y);
        val = -(1<<29);
        sum = 0;
        query(1, 1, n);
        printf("%lld\n",val);
    }




    return 0;
}