#include <iostream>
#include <fstream>
#define INF 999999999999999
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct nod{
    long long s; ///suma totala
    long long left; ///suma maxima stanga
    long long right; ///suma maxima dreapta
    long long mid; ///suma maxima mijloc

};
nod arb[500005];
int n, m;
long long sum;
int x;
int a,b;
void update(long long node, long long left, long long right, long long val, long long pos){
    if (left==right){
        arb[node].s=val;
        arb[node].left=val;
        arb[node].right=val;
        arb[node].mid=val;
        return;
    }
    long long lson=2*node;
    long long rson=2*node+1;
    long long mij=(left+right)/2;
    if (pos<=mij){
        update(lson, left, mij, val, pos);
    }
    else{
        update(rson, mij+1, right, val, pos);
    }
    arb[node].s = arb[lson].s + arb[rson].s;
    arb[node].left = max(arb[lson].left, arb[lson].s + arb[rson].left);
    arb[node].right = max(arb[rson].right, arb[rson].s+arb[lson].right);
    arb[node].mid = max ( arb[lson].right + arb[rson].left, max(arb[lson].mid, arb[rson].mid));
}
long long query(long long node, long long left, long long right, long long qleft, long long qright){
    if (qleft<=left && qright>=right){
        long long rasp = max(arb[node].mid, sum+arb[node].left);
        sum = max(sum+arb[node].s, arb[node].right);
        return rasp;
    }
    long long lson=2*node;
    long long rson=2*node+1;
    long long mij = (left+right)/2;
    long long ans=-INF;
    if (qleft<=mij){
        ans=max(ans, query(lson, left, mij, qleft, qright));
    }
    if (qright>mij){
        ans=max(ans, query(rson, mij+1, right,qleft,qright));
    }
    return ans;
}
int main()
{
    fin >> n >> m;
    for (int i=1; i<=n; ++i){
        fin >> x;
        update(1,1,n,x,i);
    }
    for (int i=1; i<=m; ++i){
        sum=-INF;
        fin >> a >> b;
        fout << query(1,1,n,a,b)<<'\n';
    }
    return 0;
}