#include <bits/stdc++.h>

using namespace std;

constexpr int kLimit = 1 << 17;
constexpr int BS = 512;
constexpr int64_t kInfinite = numeric_limits <int64_t>:: max();

int V[kLimit];
int64_t best[kLimit / BS + 1], least[kLimit / BS + 1], SPBest[kLimit / BS + 1], Partial[kLimit];

const inline int64_t query (int from, const int& to) {
    int64_t ret = -kInfinite, LeastSum = not from? 0: Partial[from - 1];

    while (from <= to and from % BS) {
            ret = max(ret, Partial[from] - LeastSum);
            LeastSum = min(LeastSum, Partial[from++]);
    }

    while (from <= to and from + BS <= to) {
          ret = max(ret, SPBest[from / BS]);
          ret = max(ret, best[from / BS] - LeastSum);
          LeastSum = min(LeastSum, least[from / BS]);
          from += BS;
    }

    while (from <= to) {
            ret = max(ret, Partial[from] - LeastSum);
            LeastSum = min(LeastSum, Partial[from++]);
    }
    return ret;
}

int main() {
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");

    int N, Q; cin >> N >> Q;

    for (int i = 0; i < N; ++i)
        cin >> V[i];

    Partial[0] = V[0];
    for (int i = 1; i < N; ++i)
        Partial[i] += Partial[i - 1] + V[i];

    for (int i = 0; i < N ; i += BS ) {
        SPBest[i / BS] = -kInfinite;
        best[i / BS] = -kInfinite;
        least[i / BS] = kInfinite;
    }

    for (int i = 0; i < N; ++i) {
        SPBest[i / BS] = max(SPBest[i / BS], Partial[i] - least[i / BS]);
        least[i / BS] = min(least[i / BS], Partial[i]);
        best[i / BS] = max(best[i / BS], Partial[i]);
    }
    while (Q--) {
          int from, to; cin >> from >> to;
          cout << query(from - 1, to - 1) << '\n';
    }
    return 0;
}