#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int N,M;
long long Array[NMAX],Sum[4*NMAX],SumA[4*NMAX],SumB[4*NMAX],SumC[4*NMAX],DP,result;
void Build(long long Node,long long L,long long R)
{
    if(L>R)
        return;
    if(L==R)
    {
        Sum[Node]=Array[L];
        SumA[Node]=SumB[Node]=SumC[Node]=Array[L];
        return;
    }
    Build(Node*2,L,(L+R)/2);
    Build(Node*2+1,(L+R)/2+1,R);
    Sum[Node]=Sum[Node*2]+Sum[Node*2+1];
    SumA[Node]=max(SumA[Node*2],Sum[Node*2]+SumA[Node*2+1]);
    SumB[Node]=max(SumB[Node*2+1],Sum[Node*2+1]+SumB[Node*2]);
    SumC[Node]=max(SumC[Node*2],SumC[Node*2+1]);
    SumC[Node]=max(SumC[Node],SumB[Node*2]+SumA[Node*2+1]);
}
void Read()
{
    int i;
    f>>N>>M;
    for(i=1;i<=N;i++)
        f>>Array[i];
}
void Query(long long Node,long long L,long long R,long long a,long long b)
{
    if(L>R || L>b || R<a)
        return ;
    if(a<=L && R<=b)
    {
        result=max(result,SumC[Node]);
        result=max(result,SumA[Node]);
        result=max(result,DP+SumA[Node]);
        result=max(result,DP);
        DP=max(SumB[Node],DP+Sum[Node]);
        return;
    }
    Query(Node*2,L,(L+R)/2,a,b);
    Query(Node*2+1,(L+R)/2+1,R,a,b);
}
int main()
{
    Read();
    Build(1,1,N);
    for(int i=1;i<=M;i++)
    {
        int x,y;
        f>>x>>y;
        result=-1000000000000;
        DP=-1000000000000;
        Query(1,1,N,x,y);
        g<<result<<"\n";
    }
    return 0;
}