#include <fstream>

using namespace std;

ifstream cin ("sequencequery.in");
ofstream cout ("sequencequery.out");

long long sp[400000];
long long stmax[400000];
long long drmax[400000];
long long smax[400000];

void Update (int nod, int st, int dr, int nr, int pos){
    if (st==dr){
        sp[nod]=1LL*nr;
        stmax[nod]=1LL*nr;
        drmax[nod]=1LL*nr;
        smax[nod]=1LL*nr;
        return;
    }
    int mij=(st + dr) / 2;
    if (pos<=mij){
        Update (nod*2, st, mij, nr, pos);
    }
    else{
        Update (nod*2+1, mij+1, dr, nr, pos);
    }
    sp[nod]=sp[nod*2]+sp[nod*2+1];
    stmax[nod]=max(stmax[nod*2], sp[nod*2] + stmax[nod*2+1]);
    drmax[nod]=max(drmax[nod*2 + 1], drmax[nod*2] + sp[nod*2+1]);
    smax[nod]=max(max(max(max(max(stmax[nod], drmax[nod]), drmax[nod*2] + stmax[nod*2 + 1]),sp[nod]),smax[nod*2]), smax[nod*2+1]);
}

void Query (int nod, int st, int dr, int MIN, int MAX, long long &partial_sum, long long &best){
    if (MIN<=st && MAX>=dr){
        if (partial_sum < 0) {
            partial_sum = 0 ;
        }
        best = max (max (best, partial_sum + stmax [nod]), smax [nod]) ;
        partial_sum = max(partial_sum + sp [nod], drmax [nod]) ;
        return ;
    }
    int mij=(st+dr) / 2;
    if (MIN<=mij){
        Query (nod*2, st, mij, MIN, MAX, partial_sum, best);
    }
    if (MAX>mij) {
        Query(nod * 2 + 1, mij + 1, dr, MIN, MAX, partial_sum, best);
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1; i<=n; i++){
        int x;
        cin>>x;
        Update(1, 1, n, x, i);
    }
    for (int i=1; i<=m; i++){
        int a,b;
        cin>>a>>b;
        long long sum = 0 ;
        long long ans = - (1 << 30) ;
        Query(1, 1, n, a, b, sum, ans) ;
        cout << ans << '\n' ;
    }
    return 0;
}