#include <cstdio>
#define max(a, b) (a > b ? a : b)

using namespace std;

struct scula {
    long long a, b, c, d;
};

int n, m, a, b, c;
int i, j, k, up;
int v[100100];
scula x[400100];

long long rez, sum;

void update(int nod, int l, int r, int poz) {
    int m = (l + r) / 2;
    
    if ( (l == r) && (l == poz) ) {
        x[nod].a = x[nod].b = x[nod].c = up;
        x[nod].d = up;
    }
    else {
        if (poz<=m)            
            update(nod*2, l, m, poz);
        else
            update(nod*2+1, m+1, r, poz);
            
        x[nod].a = max( x[2 * nod].a, x[2 * nod].d + x[2 * nod + 1].a );
        x[nod].b = max( x[2 * nod + 1].b, x[2 * nod].b + x[2 * nod + 1].d );
        x[nod].c = max( max(x[2*nod].c, x[2*nod+1].c), x[2*nod].b + x[2*nod+1].a );
        x[nod].d = x[2 * nod].d + x[2 * nod + 1].d;
    }
    
}

void query(int nod, int l, int r) {
    int m = (l + r) / 2;    
    
    if ((b <= l) && (c >= r)) {    
        if (sum < 0)
            sum = 0;
                    
        rez = max(rez, max( x[nod].c, sum+x[nod].a ) );    
        sum = max( sum + x[nod].d, x[nod].b );
    }
    else {
        if (b <= m)
            query(2*nod, l, m);
        
        if (c > m)    
            query(2*nod+1, m+1, r);
    }
}

int main() {
    
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    
    scanf("%d%d", &n, &m);
    
    for (i=1; i<=n; i++) {
        scanf("%d", &v[i]);
        up = v[i];
        update(1, 1, n, i);
    }
    
    for (i=1; i<=m; i++) {
        scanf("%d%d", &b, &c);
        
        rez = v[b];
        sum = 0;
        query(1, 1, n);
        printf("%lld\n", rez);
        
    }
        
    return 0;    
}