#include <fstream>
using namespace std;

//////////////////////////////////////

const int MAX = 1e5 + 1;

const int MINIM = 1e5 * 1e5 * (-1);

long long v[MAX] , op , a , b , n , q, prefix , sufix, summax, sum;

struct a{

    long long sum , sf , pf , smax;

}aint[4*MAX];

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

/////////////////////////////////////////////

void init( int nod , int st , int dr ){

    if( st == dr ){

        aint[nod].sum = v[st];
        aint[nod].pf = v[st];
        aint[nod].sf = v[st];
        aint[nod].smax = v[st];

    }else{

        int mij = (st+dr)/2;

        init(nod*2,st,mij);
        init(nod*2+1,mij+1,dr);

        aint[nod].sum = aint[nod*2].sum + aint[nod*2+1].sum;
        aint[nod].pf = max(aint[nod*2].pf ,aint[nod*2].sum + aint[nod*2+1].pf);
        aint[nod].sf = max(aint[nod*2+1].sf ,aint[nod*2+1].sum + aint[nod*2].sf);
        aint[nod].smax = max( aint[nod*2].sf + aint[nod*2+1].pf ,max(aint[nod*2].smax,aint[nod*2+1].smax));
    }
}

void query(int nod , int st , int dr , int qst , int qdr){

    if(qst <= st && dr <= qdr){

        summax = max(sufix + aint[nod].pf ,max(summax,aint[nod].smax));
        sufix = max(aint[nod].sf, aint[nod].sum + sufix);
        prefix = max(prefix, aint[nod].pf + sum);
        sum += aint[nod].sum;

    }else{

        int mij = (st+dr)/2;

        if(qst <= mij) query(nod*2,st,mij,qst,qdr);
        if(qdr > mij) query(nod*2+1,mij+1,dr,qst,qdr);

    }

}

int main()
{

    cin >> n >> q;

    for(int i = 1 ; i <= n ; i++){

        cin >> v[i];
    }

    init(1,1,n);

    while(q--){

        cin >> a >> b;

        prefix = sufix = sum = summax = MINIM;

        query(1,1,n,a,b);

        cout << summax << '\n';
    }

    return 0;
}