#include <stdio.h>

#define MAX_N 100010
#define lim 1 << 18
#define inf (long long)1000000 * 1000000

#define ll long long

int i,j,n,m,p2,p,q;
int op[MAX_N][3];
int nod[MAX_N],v[MAX_N];;
ll SubMax[lim], MaxSt[lim], MaxDr[lim], Sum[lim], lun, dr;

void cit() {
    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]);
    for (i = 1; i <= m; i++) 
        scanf("%d %d",&op[i][0],&op[i][1]);
}

ll maxim(ll p, ll q, ll r) {
    ll h = p;
    if (q > h) h = q;
    if (r > h) h = r;
    
    return h;
}

void actual(int k) {
     Sum[k] = Sum[k * 2] + Sum[k * 2 + 1];
     SubMax[k] = maxim(SubMax[k * 2], SubMax[k * 2 + 1], MaxDr[k * 2] + MaxSt[k * 2 + 1]);
     MaxSt[k] = maxim(MaxSt[k * 2], MaxSt[k * 2 + 1] + Sum[k * 2], -inf);
     MaxDr[k] = maxim(MaxDr[k * 2 + 1], MaxDr[k * 2] + Sum[k * 2 + 1], -inf);
}

void init(int k) {
     if (k >= p2) return;
     
     init(k * 2);
     init(k * 2 + 1);

     actual(k);
}

void query(int k, int x, int y) {

    if (x > q || y < p || k > p2 + n) return;
    if (p <= x && y <= q) nod[++nod[0]] = k;
    else {
        query(k * 2, x, (x + y) / 2);
        query(k * 2 + 1, (x + y) / 2 + 1, y);
    }
}

void solve() {
     for (p2 = 1; p2 < n; p2 *= 2) {};
     
     for (i = p2; i <= p2 + n - 1; i++) 
         MaxSt[i] = MaxDr[i] = SubMax[i] = Sum[i] = v[i - p2 + 1];
     
     init(1);
     
     for (i = 1; i <= m; i++) {
              //query
              p = op[i][0]; q = op[i][1]; nod[0] = 0;
              query(1, 1, p2);

              lun = -inf; dr = 0;
              for (j = 1; j <= nod[0]; j++) {
                    lun = maxim(lun, SubMax[nod[j]], dr + MaxSt[nod[j]]);
                    dr = maxim(MaxDr[nod[j]], dr + Sum[nod[j]], -inf);
              }
              printf("%lld\n",lun);
         }
}

int main() {

    cit();
    solve();

    return 0;
}