#include <fstream>

#define NMAX 800000

using namespace std;

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

struct arb{long long val , st , dr;} ai[NMAX] , ans;

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

void pr(int inc , int sf , int nr);
void init(int inc , int sf , int nr);
void suma(int x , int y , 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 <= NMAX ; ++i){
        ai[i].val = -100000000000;
    }

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

    pr(1 , n , 1);
    init(1 , n , 1);

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

        ans.val = -100000000000 , ok = 0;
        query(x , y , 1 , n , 1);

        g << ans.val << '\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(ok == 1){
            sol = 0;
            suma(ans.dr + 1 , ai[nr].st - 1 , 1 , n , 1);

            int aux = ans.val + sol + ai[nr].val;

            if(aux > ai[nr].val){
                ans.val = aux;
                ans.dr = ai[nr].dr;
            }

            if(ai[nr].val > ans.val){
                ans = ai[nr];
            }
        }
        else{
            ans = ai[nr];
        }

        ok = 1;
        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];

        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];
}

void suma(int x , int y , int inc , int sf , int nr){
    int mij = (inc + sf) / 2;
    if(x <= inc && sf <= y){
        sol += sum[nr];
        return ;
    }

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

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

void init(int inc , int sf , int nr){
    if(inc == sf){
        ai[nr].val = v[inc];
        ai[nr].dr = inc;
        ai[nr].st = inc;

        return;
    }

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

    if(ai[nr * 2].val > ai[nr].val){
        ai[nr] = ai[nr * 2];
    }
    if(ai[nr * 2 + 1].val > ai[nr].val){
        ai[nr] = ai[nr * 2 + 1];
    }

    sol = 0;
    suma(ai[nr * 2].dr + 1 , ai[nr * 2 + 1].st - 1 , 1 , n , 1);

    int aux = ai[nr * 2].val + ai[nr * 2 + 1].val + sol;

    if(aux > ai[nr].val){
        ai[nr].val = aux;
        ai[nr].st = ai[nr * 2].st;
        ai[nr].dr = ai[nr * 2 + 1].dr;
    }
}