#include <stdio.h>
#include <fstream>
using namespace std;

#define in "sequencequery.in"
#define out "sequencequery.out"
#define dim 100001
#define left 2*nod
#define right 2*nod+1 

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

int N, M;
int C[dim];
long long X[3*dim], Y[3*dim], Sum[3*dim], XY[3*dim];

int A, B;
long long S, maxim;

void Update(int,int,int);
void Query(int,int,int);

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &M);
    for ( int i = 1; i <= N; i++ ) 
    {
        scanf("%d", &C[i]);
        A = i;
        Update(1,1,N);
    }
    
    for ( ; M; M-- )
    {
        scanf("%d%d", &A, &B);
        S = maxim = -dim;
        Query(1,1,N);
        
        printf("%d\n", maxim);
    }
}

void Update(int nod, int st, int dr)
{
     if ( st == dr )
     {
          X[nod] = Y[nod] = Sum[nod] = XY[nod] = C[st];
          return;
     }
     
     int div = (st+dr)>>1;
     if ( A <= div ) Update(2*nod,st,div);
     else            Update(2*nod+1,div+1,dr);
     
     X[nod] = Maxim( X[left], X[right]+Sum[left] );
     Y[nod] = Maxim( Y[right], Y[left]+Sum[right] );
     XY[nod] = Maxim( Maxim(XY[left],XY[right]), X[right]+Y[left] );
     Sum[nod] = Sum[left]+Sum[right];
}

void Query(int nod, int st, int dr)
{
     if ( A <= st && dr <= B )
     {
          if ( S < 0 ) S = 0;
          maxim = Maxim(maxim, Maxim(XY[nod],S+X[nod]));
          S = Maxim( S+Sum[nod], Y[nod] );
          
          return;
     }
     
     int div = (st+dr)>>1;
     if ( A <= div ) Query(2*nod,st,div);
     if ( B > div )  Query(2*nod+1,div+1,dr);
}