#include <fstream>
#include <vector>

std::ifstream fin("sequencequery.in");
std::ofstream fout("sequencequery.out");

using namespace std;

const int oo = 0x3f3f3f3f;


vector<int> SumPart;

long long max(long long a,long long b)
{
    return a > b ? a : b;
}
struct node
{
    long long sum,pref,suff,best;
};
class ArbINT
{
    vector<node> A;
    int size_of_array,minim,cnt = 1;
public:
    ArbINT(int sz)
    {
        size_of_array = sz;
        A.resize(4*size_of_array+5,{0,0,0,0});
    }
    void Build()
    {
        BuildUtil(1,1,size_of_array);
    }
    int Querry(int st,int dr)
    {
        auto node = QuerryUtil(1,1,size_of_array,st,dr);
        return node.best;
    }
private:
    void BuildUtil(int nod,int st,int dr)
    {
        if(st == dr)
        {
            fin >> A[nod].sum;
            A[nod].pref = A[nod].sum;
            A[nod].suff = A[nod].sum;
            A[nod].best = A[nod].sum;
        }
        else
        {
            int mid = (st+dr)/2;
            BuildUtil(2*nod,st,mid);
            BuildUtil(2*nod+1,mid+1,dr);
            A[nod].sum = A[2*nod].sum + A[2*nod+1].sum;
            A[nod].pref = max(A[2*nod].sum + A[2*nod+1].pref,A[2*nod].pref);
            A[nod].suff = max(A[2*nod+1].suff,A[2*nod+1].sum + A[2*nod].suff);
            A[nod].best = max(max(A[2*nod].best,A[2*nod+1].best),A[2*nod].suff+A[2*nod+1].pref);
        }
    }
    node QuerryUtil(int nod,int st,int dr,int a,int b)
    {
        if(a <= st && dr <= b)
            return A[nod];
        else
        {
            int mid = (st+dr)/2;
            if(b <= mid)
                return QuerryUtil(2*nod,st,mid,a,b);
            if(a > mid)
                return QuerryUtil(2*nod+1,mid+1,dr,a,b);

            node left = QuerryUtil(2*nod,st,mid,a,b);
            node right = QuerryUtil(2*nod+1,mid+1,dr,a,b);

            return (node){left.sum+right.sum,max(left.pref,left.sum+right.pref),max(right.suff, right.sum+left.suff),max(max(left.best,right.best),left.suff + right.pref)};
        }
    }
};

int N,Q,maxim;

int main()
{
    fin >> N >> Q;
    ArbINT AINT(N);
    AINT.Build();

    int x,y;
    while(Q--)
    {
        fin >> x >> y;
        fout << AINT.Querry(x,y) << '\n';
    }
}