#include <cstdio>
#include <algorithm>
#define left 2*node
#define right 2*node+1
#define N 100003
#define INF 0x3f3f3f3f
using namespace std;
struct qwerty
{
    long long sum;
    long long l;
    long long r;
    long long best;
};

qwerty arb[4*N+10];

int a[N] , i , n , m , x , y;

long long prefix , sol ;

void QUERY(int node , int st , int dr , int x , int y)
{
    if( st >= x && dr <= y )
    {
        sol = max( sol, max( arb[node].best , arb[node].l + prefix ) );
        prefix = max( arb[node].r, arb[node].sum + prefix );
        return;
    }
    int mij = ( st + dr ) >> 1;
    if( x <= mij )
        QUERY( 2 * node , st , mij, x , y );
    if( y > mij )
        QUERY( 2 * node + 1 , mij + 1 , dr, x , y );
}
void BUILD(int node , int st , int dr)
{
    int mij = (st + dr) >> 1;
    if(st == dr)
    {
        arb[node].sum = arb[node].r = arb[node].l = arb[node].best = a[st];
        return;
    }
    BUILD( left, st, mij );
    BUILD( right, mij+1, dr );
    arb[node].sum = arb[left].sum + arb[right].sum;
    arb[node].best = max( arb[left].best , max(arb[right].best , arb[left].r + arb[right].l ) );
    arb[node].l = max ( arb[left].l , arb[left].sum + arb[right].l );
    arb[node].r = max ( arb[right].r , arb[right].sum + arb[left].r );

}

int main()
{
    freopen("sequencequery.in", "r" , stdin);
    freopen("sequencequery.out", "w" , stdout);
    scanf("%d%d", &n , &m);
    for(i = 1 ; i <= n ; i++)
    {
        scanf("%d", &a[i]);
    }
    BUILD(1,1,n);
    for(i = 1 ; i <= m ; i++)
    {
        scanf("%d%d", &x , &y);
        sol = prefix = -INF;
        QUERY(1,1,n,x,y);
        printf("%lld\n",sol);
    }
    return 0;
}