// in 10 minute va curge cu iPhone-uri, iPad-uri, Apple Watch-uri si MacBook-uri
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

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

const int NMAX = 1e5 + 5;

struct Node {
    int max, min, sumMax;
};

Node segmTree[4 * NMAX];
ll v[NMAX];

#define l segmTree[2 * node + 1]
#define r segmTree[2 * node + 2]
#define curr segmTree[node]

void recalc (int node) {
    curr.min = min (l.min, r.min);
    curr.max = max (l.max, r.max);
    curr.sumMax = max (r.max - l.min, max (l.sumMax, r.sumMax));
}

void build (int node, int left, int right) {
    if (left == right) {
        curr.min = (left != 0) ? v[left - 1] : 0;
        curr.max = v[left];
        curr.sumMax = curr.max - curr.min;
        return;
    }
    int mid = left + (right - left) / 2;

    build (2 * node + 1, left, mid);
    build (2 * node + 2, mid + 1, right);

    recalc (node);
}

Node recalc (Node a, Node b) {
    Node ret;
    ret.min = min (a.min, b.min);
    ret.max = max (a.max, b.max);
    ret.sumMax = max (b.max - a.min, max (a.sumMax, b.sumMax));
    return ret;
}

Node query (int node, int left, int right, int x, int y) {
    if (x <= left && right <= y) {
        return curr;
    }
    int mid = left + (right - left) / 2;

    if (y <= mid) {
        return query (2 * node + 1, left, mid, x, y);
    } else if (x > mid) {
        return query (2 * node + 2, mid + 1, right, x, y);
    } else {
        return recalc (query (2 * node + 1, left, mid, x, y), query (2 * node + 2, mid + 1, right, x, y));
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL_DEFINE
    freopen (".in", "r", stdin);
#endif
    int n, m;
	f >> n >> m;
    for (int i = 0; i < n; ++i) {
        f >> v[i];
        if (i == 0) continue;
        v[i] += v[i - 1];
    }
    build (0, 0, n - 1);
    while (m--) {
        int x, y;
        f >> x >> y;
        --x, --y;

        g << query (0, 0, n - 1, x, y).sumMax << '\n';
    }

    f.close();
    g.close();
    return 0;
}