#include <fstream>
#define NMax 200005
using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

typedef struct
{
        long long S;
        long long L;
        long long R;
        long long M;
}
ArbInt;

ArbInt A[4*NMax];
int N;

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

inline void Reuniune(ArbInt &A, ArbInt AL, ArbInt AR )
{
       A.S=AL.S+AR.S;
       A.L=Max(AL.L,AL.S+AR.L);
       A.R=Max(AR.R,AL.R+AR.S);
       A.M=Max(Max(AL.M,AR.M),AL.R+AR.L);
}
void update(int K ,int L, int R , int P , long long V)
{
       int mid = (L+R)/2;
       if(L==R)  
       {
                 A[K].S=A[K].L=A[K].R=A[K].M=V;
                 return;
       }    
       if(P<=mid) update(2*K,L,mid,P,V);
       else update(2*K+1,mid+1,R,P,V);
       Reuniune(A[K],A[2*K],A[2*K+1]);
}

ArbInt query(int K,int L,int R ,int QL,int QR)
{
       int mid=(L+R)/2;
       if(L==QL && R==QR)
       {
                return A[K];
       }
       if(QR<=mid)
       return query(2*K,L,mid,QL,QR);
       if(QL>mid)
       return query(2*K+1,mid+1,R,QL,QR);
       ArbInt Q1=query(2*K,L,mid,QL,mid);
       ArbInt Q2=query(2*K+1,mid+1,R,mid+1,QR);
       ArbInt Q;
       Reuniune(Q,Q1,Q2);
       return Q;
}


int main()
{
    int N,M;
    f>>N>>M;
    for(int i=1; i<=N ; i++)
    {      
           int X;
           f>>X;
           update(1,1,N,i,(long long)X);
    }
    for(int i=1; i<=M ; i++)
    {
            int  X,Y;
            f>>X>>Y;
            ArbInt Q = query(1,1,N,X,Y);
            g<<Q.M<<"\n";
    }
}