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

ifstream fin("C:/Radian/Programming/Buffer Infoarena/sequencequery.in");
ofstream fout("C:/Radian/Programming/Buffer Infoarena/sequencequery.out");

struct nod {
    ll sum,maxL,maxR,max;
}tree[400005];

const ll inf = 1e18;
ll sp[100005],A[100005];
ll N,M;
ll i,j,k,a,b;

void build(ll node,ll L,ll R) { 
    if (L == R){
        fin >> tree[node].sum;A[L] = tree[node].sum;
        tree[node].maxL = tree[node].maxR = tree[node].max = tree[node].sum;
    }
    else {
        ll mid = (L + R)/2;
        build(node*2,L,mid);
        build(node*2+1,mid+1,R);
        tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
        tree[node].maxL = max(tree[node*2].maxL,tree[node*2].sum + tree[node*2+1].maxL);
        tree[node].maxR = max(tree[node*2+1].maxR,tree[node*2+1].sum + tree[node*2].maxR);
        tree[node].max = max(tree[node*2].max,max(tree[node*2+1].max,tree[node*2].maxR + tree[node*2+1].maxL));
    }
}

ll query(ll node,ll L,ll R,ll touch) { // touch / -1 left / 1 right
    if (R < a || L > b)
        return -inf;
    if (L >= a && R <= b){
        if (touch == 0)
            return tree[node].max;
        if (touch == -1)
            return tree[node].maxL;
        else
            return tree[node].maxR;
    }
        
    int mid = (L + R)/2;
    if (touch == 0)
        return max(query(node*2,L,mid,0), max(query(node*2+1,mid+1,R,0), query(node*2,L,mid,1) + query(node*2+1,mid+1,R,-1) ) );
    if (touch == -1)
        return max(query(node*2,L,mid,-1), sp[mid] - sp[L-1] + query(node*2+1,mid+1,R,-1));
    else
        return max(query(node*2+1,mid+1,R,1), sp[R] - sp[mid] + query(node*2,L,mid,1));
}

int main() {
    fin >> N >> M;cout << N << " " << M;
    
    build(1,1,N);
    
    for (i = 1;i <= N;i++)
        sp[i] = sp[i-1] + A[i];
    
    for (i = 1;i <= M;i++){
        fin >> a >> b;
        fout << query(1,1,N,0) << "\n";
    }
    
}