#include<iostream>
#include<cstring>
#include<cassert>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<ctime>
#include<climits>
#include<cassert>
using namespace std;

int n, m;
long long sol, best;
int a[100100], b[300300], lf[300300], rt[300300];
#define ST 2*pos
#define DR 2*pos+1

void build(int l, int r, int pos) {
    if (l == r) {
        b[pos] = a[l];
        lf[pos] = a[l];
        rt[pos] = a[l];
        return;
    }
    int m = (l + r) / 2;
    if (l <= m) build(l, m, ST);
    if (m < r) build(m+1, r, DR);
    b[pos] = b[ST] + b[DR];
    rt[pos] = max(rt[DR], rt[ST] + b[DR]);
    lf[pos] = max(lf[ST], lf[DR] + b[ST]);
}

void query(int l, int r, int x, int y, int pos) {
    if (x <= l && r <= y) {
        best = max(best, sol + lf[pos]);
        sol = max(sol + b[pos], (long long)rt[pos]);
        sol = max(sol, (long long)0);
        return;
    }
    int m = (l + r) / 2;
    if (m >= x) query(l, m, x, y, ST);
    if (m < y) query(m+1, r, x, y, DR);
}

int main() {
    int x, y;
    
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    build(1, n, 1);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        if (x > y) swap(x, y);
        sol = 0;
        best = a[x];
        query(1,n,x,y,1);
        printf("%lld\n", best);
    }
 
    return 0;
}