#include <bits/stdc++.h>

using namespace std;

class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            bool sgn = false;
            while(not (isdigit(buffer[cursor]))) {
                sgn |= buffer[cursor] == '-';
                advance();
            }
            n = 0;
            while(isdigit(buffer[cursor])) {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            if (sgn)
                n = -n;
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};

constexpr int kLimit = 1 << 17;
constexpr int64_t kInfinite = numeric_limits <int64_t>:: max() / 4LL;
constexpr int BS = 316;

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() {
    InputReader 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] = not i ? 0 : Partial[i - 1];
    }

    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;
}