#include <bits/stdc++.h>

#define leftChild(x) (2 * x)
#define rightChild(x) (2 * x + 1)
#define ll long long
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

const ll NMax = 600003;
const ll INF = (1LL << 62);

ll n,m,s,sright,x,y;
ll a[NMax],TRmid[NMax],TRleft[NMax],TRright[NMax],SUM[NMax];

void build(ll node, ll l, ll r, ll ind, ll val){
    if(l > ind || r < ind){
        return;
    }
    if(l == ind && r == ind){
        TRmid[node] = val;      ///center
        TRleft[node] = val;     ///touching left
        TRright[node] = val;    ///touching right
        SUM[node] = val;
        return;
    }
    ll mid = (l + r) / 2;
    build(leftChild(node),l,mid,ind,val);
    build(rightChild(node),mid + 1,r,ind,val);

    ll sumLeft = max(TRleft[leftChild(node)], SUM[leftChild(node)] + TRleft[rightChild(node)]);
    ll sumRight = max(TRright[rightChild(node)], SUM[rightChild(node)] + TRright[leftChild(node)]);
    ll sumMid = max(max(sumLeft, sumRight), TRright[leftChild(node)] + TRleft[rightChild(node)]);
    sumMid = max(max(TRmid[leftChild(node)], TRmid[rightChild(node)]),sumMid);

    TRmid[node] = sumMid;
    TRleft[node] = sumLeft;
    TRright[node] = sumRight;
    SUM[node] = SUM[leftChild(node)] + SUM[rightChild(node)];
}
void query(ll node, ll l, ll r, ll a, ll b){
    if(l > b || r < a){
        return;
    }
    if(a <= l && r <= b){
        s = max(max(sright,s), max(sright + TRleft[node], TRmid[node]));
        sright = max(TRright[node], SUM[node] + sright);
        return;
    }
    ll mid = (l + r) / 2;
    query(leftChild(node),l,mid,a,b);
    query(rightChild(node),mid + 1,r,a,b);
}
int main()
{
    f >> n >> m;
    for(ll i = 1; i <= n; ++i){
        f >> a[i];
        build(1,1,n,i,a[i]);
    }
    for(ll i = 1; i <= m; ++i){
        f >> x >> y;
        s = -INF;
        sright= -INF;
        query(1,1,n,x,y);
        g << max(s,sright) << '\n';
    }
    return 0;
}