#include<bits/stdc++.h>
#define int long long
#define DIM 100000

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int n , m;
struct Iris{
    int sum , sufix , prefix , smax;
}aint[4 * DIM + 5];

inline Iris combine(Iris st , Iris dr){
    Iris rez;
    rez.sum = st.sum + dr.sum;
    rez.sufix = max(dr.sufix , dr.sum + st.sufix);
    rez.prefix = max(st.prefix , st.sum + dr.prefix);
    rez.smax = max({st.smax , dr.smax , st.sufix + dr.prefix});
    return rez;
}

inline void build(int nod , int st , int dr){
    if(st == dr){
        int x; fin >> x;
        aint[nod] = {x , x , x , x};
    }
    else{
        int mid = (st + dr) / 2;
        build(2 * nod , st , mid);
        build(2 * nod + 1 , mid + 1 , dr);
        aint[nod] = combine(aint[2 * nod] , aint[2 * nod + 1]);
    }
}

inline Iris query(int nod , int st ,int dr , int a , int b){
    if(a <= st && dr <= b) return aint[nod];
    else if(a > dr || st > b) return {0 , -10000000 , -10000000 , -10000000};
    else{
        int mid = (st + dr) / 2;
        return combine(query(2 * nod , st , mid , a , b) , query(2 * nod + 1 , mid + 1 , dr , a , b));
    }
}

signed main(){
    fin >> n >> m;
    build(1 , 1 , n);
    for(int i = 1 ; i <= m ; i++){
        int st , dr; fin >> st >> dr;
        Iris rez = query(1 , 1 , n , st , dr);
        fout << rez.smax << '\n';
    }
}