#include <iostream>
#include <fstream>
using namespace std;
#define N_MAX 100001
#define INF -999999999
int N, M, V[N_MAX];
struct ArbInt {
    int st, dr, max, S;
} Arb[4*N_MAX];
int start, finish, maxim, S;

void Build(int nod, int left, int right) {
    if(left==right) {
         Arb[nod].st=Arb[nod].dr=V[left];
         Arb[nod].max=Arb[nod].S=V[left];
         return;
    }
    
    int mij=(left+right)/2;
    Build(2*nod, left, mij);
    Build(2*nod+1, mij+1, right);
    
    Arb[nod].max=max(max(Arb[2*nod].max, Arb[2*nod+1].max), Arb[2*nod].dr + Arb[2*nod+1].st);
    Arb[nod].S=Arb[2*nod].S + Arb[2*nod+1].S;
    Arb[nod].st=max(Arb[2*nod].st, Arb[2*nod].S + Arb[2*nod+1].st);
    Arb[nod].dr=max(Arb[2*nod+1].dr, Arb[2*nod+1].S + Arb[2*nod].dr);
}

void Query(int nod, int left, int right) {
    if(start<=left && right<=finish) {
         int p=Arb[nod].max;
         maxim=max(maxim, max(Arb[nod].st+S, p));
         S=max(S+Arb[nod].S, Arb[nod].dr);
         return;
    }
    
    int mij=(left+right)/2;
    if(start<=mij) { Query(2*nod, left, mij); }
    if(mij<finish) { Query(2*nod+1, mij+1, right); }
}

int main() {
    fstream f1, f2;
    int i, j, p, q;
    f1.open("sequencequery.in", ios::in);
    f2.open("sequencequery.out", ios::out);
    f1>>N>>M;
    for(i=1; i<=N; i++) { f1>>V[i]; }
    Build(1, 1, N);
    for(i=1; i<=M; i++) {
         f1>>start>>finish;
         S=0; maxim=INF;
         Query(1, 1, N);
         f2<<maxim<<endl;
    }
    f1.close(); f2.close();
    return 0;
}