// Source: https://usaco.guide/general/io

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

const int NMAX = 1e5;
int v[NMAX + 1];

struct Node {
    int suma;
    int smax;
    int prefmax;
    int sufmax;
};

Node aint[4 * NMAX];
Node sol;

Node merge(Node a, Node b) {
    Node c = {0, (int)-1e9, (int)-1e9, (int)-1e9};

    c.suma = a.suma + b.suma;

    c.smax = a.smax;
    c.smax = max(c.smax, b.smax);
    c.smax = max(c.smax, a.sufmax + b.prefmax);

    c.prefmax = max(a.prefmax, a.suma + b.prefmax);
    
    c.sufmax = max(b.sufmax, a.sufmax + b.suma);
    return c;
}

void build(int node, int st, int dr) {
    if(st == dr) {
        aint[node].suma = v[st];
        aint[node].smax = v[st];
        aint[node].prefmax = v[st];
        aint[node].sufmax = v[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]);
    }
}

void query(int node, int st, int dr, int a, int b) {
    if(a <= st && dr <= b) {
        sol = merge(sol, aint[node]);
    } else {
        int mid = (st + dr) / 2;
        if(a <= mid) {
            query(2 * node, st, mid, a, b);
        }
        if(mid + 1 <= b) {
            query(2 * node + 1, mid + 1, dr, a, b);
        }
    }
}

signed main() {
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
	int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    build(1, 1, n);
    for(int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        sol = {0, (int)-1e9, (int)-1e9, (int)-1e9};
        query(1, 1, n, x, y);
        cout << sol.smax << '\n';
    }
}