#include <fstream>

#define In "sequencequery.in"
#define Out "sequencequery.out"

#define Nmax 100002
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define LeftSon (2*node)
#define RightSon (2*node+1)
#define Inf 0x3f3f3f3f

using namespace std;

struct _node
{
    long long LS, RS, sum, best;
};

int N, A[Nmax], x, y;
long long sum, value;
class SegmentTree
{
    public:

    inline void Build(const int node,const int left,const int right)
    {
        if(left==right)
        {
            a[node].LS = a[node].RS = a[node].best = a[node].sum = A[left];
            return;
        }
        int middle = (left+right)>>1;
        Build(LeftSon,left,middle);
        Build(RightSon,middle+1,right);
        a[node].LS = max(a[LeftSon].LS,a[LeftSon].sum + a[RightSon].LS);
        a[node].RS = max(a[RightSon].RS,a[LeftSon].RS + a[RightSon].sum);
        a[node].best = max(a[LeftSon].RS+a[RightSon].LS,max(a[RightSon].best,a[LeftSon].best));
        a[node].sum = a[LeftSon].sum + a[RightSon].sum;
    }

    inline void Query(const int node,const int left,const int right)
    {
        if(x <= left && right <= y)
        {
            if(sum<0)
                sum = 0;
            value = max(value,max(a[node].best,sum+a[node].LS));
            sum = max(sum+a[node].sum,a[node].RS);
            return ;
        }
        int middle=(left+right)>>1;
        if(x<=middle)
            Query(LeftSon,left,middle);
        if(middle<y)
            Query(RightSon,middle+1,right);
    }
    private:
    _node a[Nmax*7];
};
SegmentTree AINT;
int main()
{
    int M, i;
    ifstream f(In);
    ofstream g(Out);
    f>>N>>M;
    for(i = 1;i <= N; ++i)
        f>>A[i];
    AINT.Build(1,1,N);
    for( ;  M ; --M)
    {
        f>>x>>y;
        sum = 0;
        value = - Inf;
        AINT.Query(1,1,N);
        g<<value<<"\n";
    }
    g<<"\n";
    return 0;
}