#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 , S = 0;

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 , S = 0;
        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) {
		if (S < 0)
            S = 0;
		sol = max(sol, max(S + ainc[nr], a[nr]));
		S = max(S + sum[nr], asf[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]));
    a[nr] = max(a[nr] , max(a[nr * 2] , a[nr * 2 + 1]));
}