#include <bits/stdc++.h>

using namespace std;

int const nmax = 100000;
int const inf = 2e9;

int n , m , l , r , op;

struct aint{
int64_t pre = 0;
int64_t suf = 0;
int64_t maxs = 0;
int64_t s = 0;
}T[4 * nmax + 5];

int A[nmax + 5];

aint comp(aint a,aint b){
aint rez;
rez.s = a.s + b.s;
rez.pre = max(a.pre , a.s + b.pre);
rez.suf = max(b.suf , b.s + a.suf);
rez.maxs = max({a.maxs , b.maxs , a.suf + b.pre});
return rez;
}

void build(int i , int j , int k){
if(i != j){
    int mid = (i + j) / 2;
    build(i , mid , 2 * k);
    build(mid + 1 , j , 2 * k + 1);
    T[k] = comp(T[2 * k] , T[2 * k + 1]);
}else{
    T[k].pre = A[i];
    T[k].suf = A[i];
    T[k].maxs = A[i];
    T[k].s = A[i];
}
}

aint query(int i , int j , int k){
if(i >= l && j <= r)return T[k];
int mid = (i + j) / 2;
if(r <= mid)return query(i , mid , 2 * k);
if(l > mid)return query(mid + 1 , j , 2 * k + 1);
return comp(query(i , mid , 2 * k) , query(mid + 1 , j , 2 * k + 1));
}

int main()
{
    freopen("sequencequery.in" , "r" , stdin);
    freopen("sequencequery.out" , "w" , stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i <= n; ++i)
        cin >> A[i];
    build(1 , n , 1);
    while(m--){
        cin >> l >> r;
        cout << query(1 , n , 1).maxs << "\n";
    }
}