#include <bits/stdc++.h>
#define int long long
using namespace std;

//actualizeaza o pozitie cu o anumite valoare
//query pe interval

//actualizeaza un interval de pozitii

struct Node {
    int suma;
    int pref;
    int suf;
    int smax;
};

Node merge(Node b, Node c) {
    Node a;
    a.suma = b.suma + c.suma;
    a.pref = max(b.pref, b.suma + c.pref);
    a.suf = max(c.suf, c.suma + b.suf);
    a.smax = max(max(b.smax, c.smax), b.suf + c.pref);
    return a;
}

const int NMAX = 1e5;
const int INF = 1e15;
int a[NMAX + 1];
Node aint[4 * NMAX + 1];

void build(int node, int st, int dr) {
    
    if(st == dr) {
        aint[node].suma = a[st];
        aint[node].pref = a[st];
        aint[node].suf = a[st];
        aint[node].smax = a[st];
    } else {
        int mid = (st + dr) / 2;
        build(2 * node, st, mid);
        build(2 * node + 1, mid + 1, dr);
        aint[node] = merge(aint[2 * node], aint[2 * node + 1]);
    }
}


Node query(int node, int st, int dr, int x, int y) {
    if(x <= st && dr <= y) {
        return aint[node];
    } else {
        int mid = (st + dr) / 2;
        Node L = {-INF, -INF, -INF, -INF}; 
        Node R = {-INF, -INF, -INF, -INF};
        if(x <= mid) {
            L = query(2 * node, st, mid, x, y);
        }
        if(mid + 1 <= y) {
            R = query(2 * node + 1, mid + 1, dr, x, y);
        }
        return merge(L, R);
    }
}

signed main() {
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    for(int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << query(1, 1, n, x, y).smax << '\n';
    }
}