#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 << 1) + (n << 3) + (buffer[cursor] & 15);
                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 = 512;

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

    int const& where = (from / BS) + 1;

    if (from % BS) {
        while (from <= to and from <= where) {
            int64_t const& This = Partial[from];
            if (This - LeastSum > ret)
              ret = This - LeastSum;
            if (This < LeastSum)
              LeastSum = This;
             ++from;
    }
}

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

    while (from <= to) {
            int64_t const& This = Partial[from];
            if (This - LeastSum > ret)
              ret = This - LeastSum;
            if (This < LeastSum)
              LeastSum = This;
            ++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) {
        if (Partial[i] - least[i / BS] > SPBest[i / BS])
          SPBest[i / BS] = Partial[i] - least[i / BS];
         if (Partial[i] < least[i / BS]);
        least[i / BS] = Partial[i];
        if (Partial[i] > best[i / BS])
        best[i / BS] = Partial[i];
    }
    while (Q--) {
          int from, to; cin >> from >> to;
          cout << query(from - 1, to - 1) << '\n';
    }
    return 0;
}