#include <iostream>
#include <fstream>
#define MAX 100005

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int n, m, v[MAX], x, y;
long long A[4* MAX], B[4 * MAX], C[4 * MAX], sum[4 * MAX];

void build(int nod, int st, int dr){

    if(st == dr){
        A[nod] = B[nod] = C[nod] = v[st];
        sum[nod] = v[st];
    }
    else{
        int mij = (dr + st) / 2;
        build(nod * 2, st, mij);
        build(nod * 2 + 1, mij + 1, dr);

        A[nod] = max(A[2 * nod], A[2 * nod + 1] + sum[2 * nod]);
        B[nod] = max(B[2 * nod + 1], B[2 * nod] + sum[2 * nod + 1]);
        C[nod] = max( max(sum[2 * nod], sum[2 * nod + 1]), A[2 * nod + 1] + B[2 * nod]);

        sum[nod] = sum[2 * nod] + sum[2 * nod + 1];

    }
}

long long s, rez;
void query(int nod, int st, int dr, int x, int y){

    if( x <= st && dr <= y ){
        rez = max(rez, max(s + A[nod], C[nod]));
        s = max(s + sum[nod], B[nod]);
    }
    else{
        int mij = (dr + st) / 2;
        if(x <= mij)
            query(nod * 2, st, mij, x, y);
        if(mij + 1 <= y)
            query(nod * 2 + 1, mij + 1, dr, x, y);
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; ++i){
        fin >> v[i];
    }

    build(1, 1, n);

    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        s = 0;
        rez = -(1<<31) + 1;
        query(1, 1, n, x, y);
        fout << rez << '\n';
    }
    return 0;
}