#include <bits/stdc++.h>
using namespace std;

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

int n, m, s;
struct node{
    int sum, pref, suff, best;
};

node a[400001];

void build(int nod, int st, int dr){
    if(st == dr){
        int val;
        fin >> val;
        a[nod] = {val, val, val, val};
    }else{
        int mid = (st+dr)/2;
        build(nod*2, st, mid);
        build(nod*2+1, mid+1, dr);
        a[nod].sum = a[2*nod].sum + a[2*nod+1].sum;
        a[nod].pref = max(a[2*nod].pref, a[2*nod].sum + a[2*nod+1].pref);
        a[nod].suff = max(a[2*nod+1].suff, a[2*nod+1].sum + a[2*nod].suff);
        a[nod].best = max({a[2*nod+1].best, a[2*nod].best, a[nod*2].suff + a[nod*2+1].pref});
    }
}

node query(int nod, int st, int dr, int x, int y){
    if(st >= x && dr <= y){
        return a[nod];
    }else{
        int mid = (st+dr)/2;
        if(y <= mid)
            return query(2*nod, st, mid, x, y);
        if(x > mid)
            return query(2*nod+1, mid+1, dr, x, y);
            
        node rs = query(2*nod, st, mid, x, y);
        node rd = query(2*nod+1, mid+1, dr, x, y);
    
        return (node){rs.sum + rd.sum, max(rs.pref, rs.sum + rd.pref), max(rd.suff, rd.sum + rs.suff), max({rs.best, rd.best, rs.suff+rd.pref})};
    }
}

int main(){
    fin >> n >> m;
    build(1, 1, n);
    for(int i = 0; i < m; ++i){
        int x, y;
        fin >> x >> y;
        node s = query(1, 1, n, x, y);
        fout << s.best << "\n";
    }
}