#include<cstdio>
#include<algorithm>

using namespace std;

const int INF = 1<<29;
const int NMAX = 131072+5;

struct Node
{
    int LeftSum,RightSum,MaxSum,TotalSum;
    Node()
    {
        LeftSum = RightSum = MaxSum = TotalSum = 0;
    }
};

int N,M,K,L,R;
Node AInt[2*NMAX];
Node MIN;

Node Query(int lo,int hi,int node)
{
    if(hi<L || R<lo)
        return MIN;

    if(L<=lo && hi<=R)
        return AInt[node];

    int mi=(lo+hi)/2;
    Node A,B,C;

    A=Query(lo,mi,2*node);
    B=Query(mi+1,hi,2*node+1);

    C.TotalSum = A.TotalSum + B.TotalSum;
    C.MaxSum = max(max(A.MaxSum,B.MaxSum),A.RightSum+B.LeftSum);
    C.LeftSum = max(A.LeftSum,A.TotalSum + B.LeftSum);
    C.RightSum = max(B.RightSum,B.TotalSum + A.RightSum);

    return C;
}

int main()
{
    int i,x;

    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    scanf("%d%d",&N,&M);

    for(K=1; K<N; K<<=1);
    K--;

    for(i=1; i<=N; i++)
    {
        scanf("%d",&x);
        AInt[K+i].LeftSum = AInt[K+i].RightSum = AInt[K+i].MaxSum = AInt[K+i].TotalSum = x;
    }

    for(i=K; i>=1; i--)
    {
        L=2*i;
        R=2*i+1;
        AInt[i].TotalSum = AInt[L].TotalSum + AInt[R].TotalSum;
        AInt[i].MaxSum = max(max(AInt[L].MaxSum,AInt[R].MaxSum),AInt[L].RightSum + AInt[R].LeftSum);
        AInt[i].LeftSum = max(AInt[L].LeftSum,AInt[L].TotalSum+AInt[R].LeftSum);
        AInt[i].RightSum = max(AInt[R].RightSum,AInt[R].TotalSum+AInt[L].RightSum);
    }

    MIN.LeftSum = MIN.RightSum = MIN.MaxSum = MIN.TotalSum = -INF;

    for(;M;--M)
    {
        scanf("%d%d",&L,&R);
        printf("%d\n",Query(1,K+1,1).MaxSum);
    }

    return 0;
}