#include <iostream>
#include <fstream>

using namespace std;

const int Q=1<<20;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

struct nod1
{
    long long int maxsum;
    long long int sum;
    long long int prefsum;
    long long int sufsum;
};

long long int n,a,m;
nod1 arb[Q];

void update(int nod,int st,int dr,int index,int value)
{
    if (st == dr)
    {
        arb[nod].maxsum = arb[nod].prefsum = arb[nod].sufsum = arb[nod].sum = value;
        return ;
    }
    int mid = (st+dr)/2;
    if (index <= mid)
        update(2*nod,st,mid,index,value);
    else
        update(2*nod+1,mid+1,dr,index,value);

    arb[nod].sum = arb[2*nod].sum + arb[2*nod+1].sum;

    arb[nod].prefsum = max(arb[2*nod].prefsum, arb[2*nod].sum + arb[2*nod + 1].prefsum);

    arb[nod].sufsum = max(arb[2*nod+1].sufsum, arb[2*nod+1].sum + arb[2*nod].sufsum);
    arb[nod].maxsum = max(arb[2*nod].maxsum, max(arb[2*nod+1].maxsum, arb[2*nod].sufsum + arb[2*nod+1].prefsum));
}

long long int rez,d;

void query(int nod,int st,int dr,int a,int b)
{
    if (b < st || a > dr)
    {
        return ;
    }
    if (a <= st && dr <= b)
    {
        if (rez < arb[nod].maxsum)
        {
            rez = arb[nod].maxsum;
        }
        if (rez < d + arb[nod].prefsum)
        {
            rez = d + arb[nod].prefsum;
        }

        d = max(d + arb[nod].sum, arb[nod].sufsum);

        if (d > rez)
        {
            rez = d;
        }
        return ;
    }

    int mid = (st+dr)/2;
    query(2*nod, st,mid,a,b);
    query(2*nod+1,mid+1,dr,a,b);
}

int main()
{
    in >> n >> m;
    for (int i=1; i<=n; i++)
    {
        in >> a;
        update(1,1,1<<18,i,a);
    }
    int op,a,b;
    for (int i=1; i<=m; i++)
    {
        in >> a >> b;
        rez = INT_MIN;
        d = 0;
        query(1,1,1<<18,a,b);
        out << rez << "\n";
    }
    return 0;
}