#include <iostream>
using namespace std;
#define N_MAX 100001
#define INF -999999999
int N, M, V[N_MAX];
struct ArbInt {
    long long st, dr, max, S;
} Arb[4*N_MAX];
int start, finish;
long long 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) {
         long long 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() {
    FILE *f1=fopen("sequencequery.in", "r"), *f2=fopen("sequencequery.out", "w");
    int i, j, p, q;
    fscanf(f1, "%d%d", &N, &M);
    for(i=1; i<=N; i++) { fscanf(f1, "%d", &V[i]); }
    Build(1, 1, N);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d%d", &start, &finish);
         S=0; maxim=INF;
         Query(1, 1, N);
         fprintf(f2, "%lld\n", maxim);
    }
    fclose(f1); fclose(f2);
    return 0;
}