#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 1e5;

ll v[nmax+5];

struct Node {
    ll whole = 0;
    ll prefix = 0;
    ll sufix = 0;
    ll ans = 0;
    int mx = -1e9;
}aint[4*nmax+5];

Node Merge(Node left, Node right) {
    Node temp;
    temp.whole = left.whole + right.whole;
    temp.prefix = max(left.prefix, left.whole + right.prefix);
    temp.sufix = max(right.sufix, right.whole + left.sufix);
    temp.ans = max( max(left.ans, right.ans), left.sufix + right.prefix);
    temp.mx = max(left.mx, right.mx);
    return temp;
}

void Build(int node, int left, int right) {
    if(left == right) {
        aint[node].whole = v[left];
        aint[node].prefix = max(0LL, v[left]);
        aint[node].sufix = max(0LL, v[left]);
        aint[node].ans = max(0LL, v[left]);
        aint[node].mx = v[left];
        return ;
    }
    int mid = (left + right) / 2;
    Build(node*2, left, mid);
    Build(node*2+1, mid+1, right);
    aint[node] = Merge(aint[node*2], aint[node*2+1]);
}

Node temp;
void Query(int node, int left, int right, int st, int dr) {
    if(st <= left and right <= dr) {
        temp = Merge(temp, aint[node]);
        return;
    }
    int mid = (left + right) / 2;
    if(mid>=st) Query(node*2, left, mid, st, dr);
    if(mid<dr) Query(node*2+1, mid+1, right, st, dr);
}

int main() {
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");

    int n, q; f >> n >> q;
    for(int i=1; i<=n; i++) f >> v[i];
    Build(1, 1, n);
    cout << aint[1].ans << "\n";
    for(int i=1; i<=q; i++) {
        int st, dr; f >> st >> dr;
        temp.whole = 0; temp.prefix = 0; temp.sufix = 0; temp.ans = 0; temp.mx = -1e9;
        Query(1, 1, n, st, dr); 
        g << (temp.ans!=0 ? temp.ans : temp.mx) << "\n";
    }
    return 0;
}