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

string file = "number";
ifstream fin(file + ".in");
ofstream fout(file + ".out");

int n, m;

struct node{

    long long maxSum, maxSumLeft, maxSumRight;
    long long totalSum;

    node() {

        maxSum = maxSumRight = maxSumLeft = 0;
        totalSum = 0;
    }

    node(long long val) {

        maxSum = maxSumLeft = maxSumRight = val;
        totalSum = val;
    }
} rmq[100001][17];

inline node unit(node& a, node& b) {

    node ret;
    ret.totalSum = a.totalSum + b.totalSum;
    ret.maxSum = max(a.maxSum, b.maxSum);
    ret.maxSum = max(ret.maxSum, a.maxSumRight + b.maxSumLeft);
    ret.maxSumLeft = max(a.maxSumLeft, a.totalSum + b.maxSumLeft);
    ret.maxSumRight = max(b.maxSumRight, b.totalSum + a.maxSumRight);
    return ret;
}

inline void generateRMQ() {

    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            rmq[i][j] = unit(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}

inline node maxim(int x, int y) {

    node ret = node(LLONG_MIN >> 1);

    for (int k = 16; k >= 0; k--) {

        if (x + (1 << k) - 1 > y)
            continue;

        ret = unit(ret, rmq[x][k]);
        x += (1 << k);
    }

    return ret;
}

int main() {

    int q;
    fin >> n >> q;
    for (int i = 1; i <= n; i++) {

        int x;
        fin >> x;
        rmq[i][0] = node(x);
    }

    generateRMQ();

    for (int i = 1; i <= q; i++) {

        int x, y;
        fin >> x >> y;

        fout << maxim(x, y).maxSum << '\n';
    }

    return 0;
}