#include <fstream>

#define NMAX 800000

using namespace std;

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

long long a[NMAX] , ainc[NMAX] , asf[NMAX];

long long n , m , v[NMAX] , sum[NMAX] , sol , x , y , ok;

void pr(int inc , int sf , int nr);
void query(int x , int y , int inc , int sf , int nr);

int main()
{
    f >> n >> m;

    for(int i = 1 ; i <= n ; ++i){
        f >> v[i];
    }

    pr(1 , n , 1);

    for(int i = 1 ; i <= m ; ++i){
        f >> x >> y;

        sol = -100000000000;
        query(x , y , 1 , n , 1);

        g << sol << '\n';
    }
    return 0;
}

void query(int x , int y , int inc , int sf , int nr){
    int mij = (inc + sf) / 2;
    if(x <= inc && sf <= y){

        sol = max(sol , a[nr]);
        return ;
    }

    if(x <= mij){
        query(x , y , inc , mij , nr * 2);
    }

    if(y >= mij + 1){
        query(x , y , mij + 1 , sf , nr * 2 + 1);
    }
}


void pr(int inc , int sf , int nr){
    if(inc == sf){
        sum[nr] = v[inc];
        ainc[nr] = v[inc];
        asf[nr] = v[inc];
        a[nr] = v[inc];

        return;
    }

    pr(inc , (inc + sf) / 2 , nr * 2);
    pr((inc + sf) / 2 + 1 , sf , nr * 2 + 1);

    sum[nr] = sum[nr * 2] + sum[nr * 2 + 1];
    ainc[nr] = max(ainc[nr * 2] , sum[nr * 2] + ainc[nr * 2 + 1]);
    asf[nr] = max(asf[nr * 2 + 1] , sum[nr * 2 + 1] + asf[nr * 2]);
    a[nr] = max(ainc[nr] , max(asf[nr] , asf[nr * 2] + ainc[nr * 2 + 1]));
}