o60_oct_c1_house

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10;
int ar[N];

typedef struct Node{
    int frnt, bck, total, mx;
};

Node tree[524288];

Node Cal(Node L, Node R){
    Node cur;
    cur.frnt = max(L.frnt, L.total + R.frnt);
    cur.bck = max(R.bck, R.total + L.bck);
    cur.total = L.total + R.total;
    cur.mx = max({L.mx, R.mx, L.bck + R.frnt});
    return cur;
}

void Build(int idx, int l, int r){
    if(l == r){
        tree[idx].bck = tree[idx].frnt = tree[idx].total = tree[idx].mx = ar[l];
        return;
    }
    int mid = (l + r) / 2;
    Build(2 * idx, l, mid);
    Build(2 * idx + 1, mid + 1, r);
    tree[idx] = Cal(tree[2 * idx], tree[2 * idx + 1]);
}

Node Query(int idx, int l, int r, int s, int e){
    if(l > e or r < s) return {0, 0, 0, 0};
    if(s <= l and r <= e) return tree[idx];
    int mid = (l + r) / 2;
    return Cal( Query(2 * idx, l, mid, s, e) , Query(2 * idx + 1, mid + 1, r, s, e) );
}

int main(){

    int n, Q;
    scanf("%d %d", &n, &Q);

    for(int i=1;i<=n;i++){
        scanf("%d", &ar[i]);
    }

    Build(1, 1, n);

    for(int q=1;q<=Q;q++){
        int a, b;
        scanf("%d %d", &a, &b);
        a ++, b ++;

        Node query = Query(1, 1, n, a, b);
        printf("%d\n", query.mx);

        /*int ans = 0;
        int dpp = 0;
        for(int i=a;i<=b;i++){
            int dpc = max(dpp + ar[i], ar[i]);
            dpp = dpc;
            ans = max(ans, dpc);
        }
        printf("%d\n", ans);*/
    }

    return 0;
}