#include <fstream>
#include <vector>

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

using namespace std;

const int oo = 0x3f3f3f3f;

int max(int a,int b)
{
    return a > b ? a : b;
}
int min(int a,int b)
{
    return a < b ? a : b;
}
vector<int> SumPart;
class ArbINT
{
    vector<int> A;
    int size_of_array,minim,cnt = 1;
public:
    ArbINT(int sz)
    {
        size_of_array = sz;
        A.resize(4*size_of_array+5);
    }
    void Build()
    {
        BuildUtil(1,1,size_of_array);
    }
    int Querry(int st,int dr)
    {
        minim = oo;
        QuerryUtil(1,1,size_of_array,st,dr);
        return minim - SumPart[st-1];
    }
private:
    void BuildUtil(int nod,int st,int dr)
    {
        if(st == dr)
        {
            A[nod] = SumPart[cnt];
            cnt++;
        }
        else
        {
            int mid = (st+dr)/2;
            BuildUtil(2*nod,st,mid);
            BuildUtil(2*nod+1,mid+1,dr);
            A[nod] = min(A[2*nod],A[2*nod+1]);
        }
    }
    void QuerryUtil(int nod,int st,int dr,int a,int b)
    {
        if(a <= st && dr <= b)
        {
            minim = min(minim,A[nod]);
        }
        else
        {
            int mid = (st+dr)/2;
            if(a <= mid)
                QuerryUtil(2*nod,st,mid,a,b);
            if(b > mid)
                QuerryUtil(2*nod+1,mid+1,dr,a,b);
            //A[nod] = min(A[2*nod],A[2*nod+1]);
        }
    }
};

int N,Q,maxim;

int main()
{
    fin >> N >> Q;
    SumPart.resize(N+1,0);

    for(int i = 1; i <= N; ++i)
    {
        fin >> SumPart[i];
        SumPart[i] += SumPart[i-1];
    }
    ArbINT AINT(N);
    AINT.Build();

    int st,dr;
    while(Q--)
    {
        fin >> st >> dr;
        maxim = SumPart[st] - SumPart[st-1];
        for(int i = st + 1; i <= dr; ++i)
            maxim = max(maxim,SumPart[i] - SumPart[st-1] - AINT.Querry(st,i - 1));
        fout << maxim << '\n';
    }
}