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

ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");

const int maxn = 1e5 + 5;
int n, m;

struct Tree_node {
    long long left, right, mid, sum;
    Tree_node () {
        left = right = mid = -20000000000000000LL;
        sum = 0LL;
    }
    Tree_node (long long x) {
        left = right = mid = sum = x;
    }
} T[maxn << 1];

inline Tree_node Unite (Tree_node a, Tree_node b) {
    Tree_node ans;
    ans.sum = a.sum + b.sum;
    ans.left = max(a.left, a.sum + b.left);
    ans.right = max(b.right, a.right + b.sum);
    ans.mid = max(max(a.mid, b.mid), a.right + b.left);
    ans.mid = max(max(ans.left, ans.right), ans.mid);
    return ans;
}

inline void Build () {
    for (int i = n - 1; i > 0; i--)
        T[i] = Unite(T[i << 1], T[i << 1 | 1]);
}

inline long long Query (int left, int right) {
    Tree_node x, y;
    left += n - 1;
    right += n ;
    while (left < right) {
        if (left & 1) x = Unite(x, T[left++]);
        if (right & 1) y = Unite(T[--right], y);
        left >>= 1;
        right >>= 1;
    }

    return Unite(x, y).mid;
}

int main () {
    ios_base :: sync_with_stdio (false);
    long long x;
    int i, a, b;
    fin >> n >> m;
    for (i = 0; i < n; i++) {
        fin >> x;
        T[i + n] = Tree_node(x);
    }
    Build();
    while (m--) {
        fin >> a >> b;
        fout << Query(a, b) << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}