#include <fstream>
using namespace std;
const int MAX_N = 100002;
const long long int INF = 999999999999999LL;
struct Node {
long long int leftSum, rightSum, totalSum, ans;
};
int N, M;
Node A[2*MAX_N];
inline void update(int node, int left, int right, int x, int value) {
if(left == right)
A[node].leftSum = A[node].rightSum = A[node].totalSum = A[node].ans = value;
else {
int m = (left + right)/2;
if(x <= m)
update(2*node, left, m, x, value);
if(x > m)
update(2*node + 1, m + 1, right, x, value);
A[node].leftSum = max(A[2*node].leftSum, A[2*node].totalSum + A[2*node + 1].leftSum);
A[node].rightSum = max(A[2*node + 1].rightSum, A[2*node + 1].totalSum + A[2*node].rightSum);
A[node].totalSum = A[2*node].totalSum + A[2*node + 1].totalSum;
A[node].ans = max(max(A[2*node].ans, A[2*node + 1].ans), A[2*node + 1].leftSum + A[2*node].rightSum);
}
}
inline Node query(int node, int left, int right, int x, int y) {
if(x <= left && right <= y)
return A[node];
else {
int m = (left + right)/2;
Node temp1, temp2, temp3;
if(x <= m)
temp1 = query(2*node, left, m, x, y);
if(y > m)
temp2 = query(2*node + 1, m + 1, right, x, y);
if(x <= m && y > m) {
Node temp;
temp.totalSum = temp1.totalSum + temp2.totalSum;
temp.leftSum = max(temp1.leftSum, temp1.totalSum + temp2.leftSum);
temp.rightSum = max(temp2.rightSum, temp2.totalSum + temp1.rightSum);
temp.ans = max(temp1.ans, temp2.ans);
temp.ans = max(temp.ans, temp2.leftSum + temp1.rightSum);
return temp;
}
else if(x <= m)
return temp1;
else return temp2;
}
}
int main() {
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
f >> N >> M;
for(int i = 1, x; i <= N; ++i) {
f >> x;
update(1, 1, N, i, x);
}
for(int i = 1, x, y; i <= M; ++i) {
f >> x >> y;
g << query(1, 1, N, x, y).ans << "\n";
}
f.close();
g.close();
return 0;
}