#define NMAX 100005
#include <fstream>
#include <vector>
using namespace std;

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

int n, m;
int a[NMAX];
int x, y;


class Arbore{
private:
    struct nod{
        long long sum_inceput_interval;
        long long sum_final_interval;
        long long sum_max_din_interval;
        long long sum_total;

        nod(){
            this->sum_final_interval = 0;
            this->sum_inceput_interval = 0;
            this->sum_max_din_interval = 0;
            this->sum_total = 0;
        }
        nod operator+(nod b){
            nod rez;
            rez.sum_total=sum_total+b.sum_total;
            rez.sum_inceput_interval = max(sum_inceput_interval, sum_total + b.sum_inceput_interval);
            rez.sum_final_interval = max(sum_final_interval+b.sum_total, b.sum_final_interval);
            rez.sum_max_din_interval = max(sum_final_interval+b.sum_inceput_interval, max(sum_max_din_interval, b.sum_max_din_interval));
            return rez;
        }
    };
public:
    vector<nod> arbore_intervale;
    void adaugare(int st, int dr, int poz){
        if(st == dr){
            arbore_intervale[poz].sum_total = a[st];
            arbore_intervale[poz].sum_inceput_interval = a[st];
            arbore_intervale[poz].sum_final_interval = a[st];
            arbore_intervale[poz].sum_max_din_interval = a[st];
            return;
        }
        int mij = (st+dr)/2;
        adaugare(st, mij, poz*2);
        adaugare(mij+1, dr, poz*2+1);
        arbore_intervale[poz] = arbore_intervale[poz*2] + arbore_intervale[poz*2+1];
    }

    nod suma_maxima(int st, int dr, int a1, int b, int poz){
        if(a1<=st && b>=dr){
            return arbore_intervale[poz];
        }
        nod maxst, maxdr;
        int mij = (st + dr)/2;
        if(a1>mij){
            maxdr = suma_maxima(mij+1, dr, a1, b, poz*2+1);
            return maxdr;
        }
        else if(b<=mij){
            maxst = suma_maxima(st, mij, a1, b, poz*2);
            return maxst;
        }
        else {
            maxdr = suma_maxima(mij+1, dr, a1, b, poz*2+1);
            maxst = suma_maxima(st, mij, a1, b, poz*2);
            return maxst + maxdr;
        }
    }
    void form(int n){
        arbore_intervale.resize(4*n);
        adaugare(1, n, 1);
    }
    long long sol(int a, int b){
        return suma_maxima(1, n, a, b, 1).sum_max_din_interval;
    }
}arb;



int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++){
        f>>a[i];
    }
    arb.form(n);
    for(int i=1; i<=m; i++){
        f>>x>>y;

        g<<arb.sol(x, y)<<'\n';

    }
    return 0;
}