#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
#define DIM 666013
char buff[DIM];
int BP = DIM-1;

void SCANF(int &NR)
{
     NR = 0;
     int semn = 1;
     while ((buff[BP] < '0' || buff[BP] > '9')&&buff[BP] != '-')
          if (++BP == DIM)
               fread(buff,1,DIM,stdin),BP=0;
     while ('0'<=buff[BP] && buff[BP]<='9' || buff[BP] == '-')
     {
         if(buff[BP] == '-')
            semn *= -1;
         else
            NR = NR*10 + buff[BP] - '0';
         if (++BP == DIM)
            fread(buff,1,DIM,stdin),BP=0;
     }
     NR *= semn;
}

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(N),SCANF(M);
    for(int i = 1; i <= N; ++i)
        SCANF(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(A),SCANF(B);
        val = -INF;
        suma = 0;
        Aint.Querry(1,N,1);
        printf("%lld\n",val);
    }
    return 0;
}