#include <cstdio> //fopen, fscanf, fgetc, fread
#include <cctype> //isdigit
#include <algorithm> //max
#define NMAX 100000
#define BUF_SIZE 1 << 17
using namespace std;
FILE *fin = fopen("sequencequery.in", "r");
FILE *fout = fopen("sequencequery.out", "w");
char buf[BUF_SIZE]; //bufferul
int pos = BUF_SIZE;
inline char nextch(){
if(pos == BUF_SIZE){
fread(buf, BUF_SIZE, 1, fin); //mai intai vectorul, apoi dimensiunea, apoi cifra 1, apoi fisierul
pos = 0; //fixam pozitia de la care incepem sa citim ca 0
}
return buf[pos++]; //returneaza buf[pos], dupa care creste pos
}
inline int read(){
char ch = nextch();
while( !isdigit(ch) && ch != '-' ){
ch = nextch();
}
int semn = 1; //pozitiv
if(ch == '-'){
semn = -1;
ch = nextch();
}
int nr = 0;
while( isdigit(ch) ){
nr = nr * 10 + ch - '0';
ch = nextch();
}
return semn * nr;
}
struct element{
long long maxIndSum; //max independent de unde se afla
long long leftSum, rightSum;
long long totSum;
};
int X, Y;
int v[NMAX + 1];
element tree[4 * NMAX + 1];
element rezultat(element A, element B, int dim1, int dim2){
element rez;
rez.maxIndSum = max(A.maxIndSum, B.maxIndSum);
//if(A.rightSum > 0 && B.leftSum > 0){
//cel din mijloc devine un candidat pt suma independenta
rez.maxIndSum = max(rez.maxIndSum, A.rightSum + B.leftSum);
rez.leftSum = max(A.leftSum, A.totSum + B.leftSum);
rez.rightSum = max(B.rightSum, B.totSum + A.rightSum);
rez.totSum = A.totSum + B.totSum;
return rez;
}
void buildArbore(int node, int left, int right){
if(left == right){
tree[node].leftSum = v[left];
tree[node].rightSum = v[left];
tree[node].maxIndSum = v[left];
tree[node].totSum = v[left];
return;
}
int mid = left + (right - left) / 2;
buildArbore(node * 2, left, mid);
buildArbore(node * 2 + 1, mid + 1, right);
tree[node] = rezultat(tree[node * 2], tree[node * 2 + 1], mid - left + 1, right - mid);
}
element query(int node, int left, int right){
if(X <= left && right <= Y){
return tree[node];
}
int mid = left + (right - left) / 2;
element aux1, aux2;
int OK1 = 0, OK2 = 0;
if(X <= mid){
//e relevant si fiul din stanga
aux1 = query(node * 2, left, mid);
OK1 = 1;
}
if(mid + 1 <= Y){
//e relevant si fiul din dreapta
aux2 = query(node * 2 + 1, mid + 1, right);
OK2 = 1;
}
if(OK1 == 1 && OK2 == 1){
return rezultat(aux1, aux2, mid - left + 1, right - mid); //daca le am pe ambele
}
else if(OK1 == 1){
return aux1;
}
else {
return aux2;
}
}
int main()
{
/*
//testez functia rezultat();
element A;
A.leftSize = 3;
A.rightSize = 3;
A.maxIndSum = 30;
A.leftSum = 30;
A.rightSum = 30;
element B;
B.leftSize = 1;
B.rightSize = 2;
B.maxIndSum = 10;
B.leftSum = 3;
B.rightSum = 9;
element AUB;
AUB = rezultat(A, B, 3, 7);
cout << AUB.leftSize << "\n" << AUB.rightSize << "\n" << AUB.maxIndSum << "\n" << AUB.leftSum << "\n" << AUB.rightSum;
*/
int N, M;
N = read();
M = read();
for(int i = 1; i <= N; i++){
v[i] = read();
}
buildArbore(1, 1, N);
for(int q = 1; q <= M; q++){
X = read();
Y = read();
element aux = query(1, 1, N);
fprintf(fout, "%lld\n", aux.maxIndSum);
}
return 0;
}