#include <cstdio>
#include <algorithm>

#define Nmax 100005
#define dMAX ((1<<20)+666)
#define left_son (pz<<1)
#define right_son ((pz<<1)|1)
#define INF 0x3f3f3f3f

using namespace std;

int v[Nmax],A,B,N,M;
long long suma,val;

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

void read()
{
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; ++i)
        scanf("%d",&v[i]);
}
struct nod{
    int LS,RS,sum,best;
};

class SegmentTree{
private:
    nod D[dMAX];
public:
    inline void Build(int li,int lf,int pz)
    {
        if(li == lf)
        {
            D[ pz ].LS = D[ pz ].RS = D[ pz ].sum = D[ pz ].best = v[li];
            return;
        }
        int m = li +((lf-li)>>1);
        Build(li,m,left_son);
        Build(m+1,lf,right_son);
        D[ pz ].LS = maxi(D[left_son].LS,D[left_son].sum+D[right_son].LS);
        D[ pz ].RS = maxi(D[right_son].RS,D[right_son].sum+D[left_son].RS);
        D[ pz ].best = maxi(D[left_son].RS+D[right_son].LS,maxi(D[left_son].best,D[right_son].best));
        D[ pz ].sum = D[left_son].sum + D[right_son].sum;
    }
    inline void Querry(int li,int lf,int pz)
    {
        if(A <= li && lf <= B)
        {
            if(suma < 0)
                suma = 0;
            val = maxi(val,maxi(D[pz].best,suma+D[pz].LS));
            suma = maxi(suma+D[pz].sum,D[pz].RS);
            return;
        }
        int m = li + ((lf-li)>>1);
        if(A <= m)
            Querry(li,m,left_son);
        if(B > m)
            Querry(m+1,lf,right_son);
    }
};
SegmentTree Aint;

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

    read();
    Aint.Build(1,N,1);
    while(M--){
        scanf("%d%d",&A,&B);
        val = -INF;
        suma = 0;
        Aint.Querry(1,N,1);
        printf("%d\n",val);
    }
    return 0;
}