#include <bits/stdc++.h>
#define NMAX 100005
 
using namespace std;
 
/*******************************/
// PARSARE

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
/*******************************/
// INPUT / OUTPUT
 
InParser fin("sequencequery.in");
ofstream g("sequencequery.out");
/*******************************/
/// GLOBAL DECLARATIONS
 
int N, M;
bool primul;
struct Node
{
    long long sum, leftSum, rightSum, ssm;
} arb[4 * NMAX];
Node ans;
/*******************************/
/// FUNCTIONS
 
void ReadInput();
void Solution();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    fin >> N >> M;
}
///-------------------------------------
void Update(int st, int dr, int idx, int pos, long long val)
{
    if (st == dr)
    {
        arb[idx].sum = val;
        arb[idx].leftSum = val;
        arb[idx].rightSum = val;
        arb[idx].ssm = val;
        return;
    }
 
    int mij = (st + dr) / 2;
 
    if (pos <= mij) Update(st, mij, 2 * idx, pos, val);
    else Update(mij + 1, dr, 2 * idx + 1, pos, val);
 
    arb[idx].sum = arb[2 * idx].sum + arb[2 * idx + 1].sum;
    arb[idx].ssm = max(arb[2 * idx].ssm, max(arb[2 * idx + 1].ssm, arb[2 * idx].rightSum + arb[2 * idx + 1].leftSum));
    arb[idx].leftSum = max(arb[2 * idx].leftSum, arb[2 * idx].sum + arb[2 * idx + 1].leftSum);
    arb[idx].rightSum = max(arb[2 * idx + 1].rightSum, arb[2 * idx + 1].sum + arb[2 * idx].rightSum);
}
///-------------------------------------
void Query(int arbSt, int arbDr, int st, int dr, int idx)
{
    if (dr < arbSt || st > arbDr)
    {
        return;
    }
    
    if (st <= arbSt && dr >= arbDr)
    {
        if (primul)
        {
            ans.ssm = arb[idx].ssm, ans.rightSum = arb[idx].rightSum;
            primul = false;
        }
        else
        {
            ans.ssm = max(ans.ssm, max(arb[idx].ssm, ans.rightSum + arb[idx].leftSum));
            ans.rightSum = max(arb[idx].rightSum, ans.rightSum + arb[idx].sum);
        }
        return;
    }
 
    int mij = (arbSt + arbDr) / 2;
    
    Query(arbSt, mij, st, dr, 2 * idx);
    Query(mij + 1, arbDr, st, dr, 2 * idx + 1);
    return;
}
///-------------------------------------
inline void Solution()
{
    long long num;
    for (int i = 1 ; i <= N ; ++ i)
    {
        fin >> num;
        Update(1, N, 1, i, num);
    }
 
    int a, b;
    while (M --)
    {
        fin >> a >> b;
        primul = true;
        Query(1, N, a, b, 1);
        g << ans.ssm << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    return 0;
}