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

#define in "sequencequery.in"
#define out "sequencequery.out"
#define dim 100001
#define st (nod<<1)
#define dr (st+1) 

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

int N, M;
int C[dim];
int St[3*dim], Dr[3*dim], Sum[3*dim], V[3*dim];

int A, B;
int 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 left, int right)
{
     if ( left == right )
     {
          St[nod] = Dr[nod] = Sum[nod] = V[nod] = C[left];
          return;
     }
     
     int div = (left+right)>>1;
     if ( A <= div ) Update(2*nod,left,div);
     else            Update(2*nod+1,div+1,right);
     
     St[nod] = Maxim( St[st], Sum[st]+St[dr] );
     Dr[nod] = Maxim( Dr[dr], Sum[dr]+Dr[st] );
     V[nod] = Maxim( St[st]+Dr[dr], Maxim(V[st],V[dr]) );
     Sum[nod] = Sum[st] + Sum[dr];
}

void Query(int nod, int left, int right)
{
     if ( A <= left && right <= B )
     {
          S = Maxim(0,S);
          maxim = Maxim( maxim, Maxim(S+St[nod],V[nod]) );
          S = Maxim( Sum[nod]+S, Dr[nod] );
          
          return;
     }
     
     int div = (left+right)>>1;
     if ( A <= div ) Query(2*nod,left,div);
     if ( B > div )  Query(2*nod+1,div+1,right);
}