#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

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

long long v[NMAX], smaxleft[4*NMAX],smaxright[4*NMAX],stotal[4*NMAX],smax[4*NMAX],x,y,res,sum;

void build_ai(int poz, int st, int dr) {
	if(st==dr) {
		smaxleft[poz]=smaxright[poz]=stotal[poz]=smax[poz]=v[st];
		return;
	}

	int fs=poz<<1, mid=(st+dr)>>1;
	build_ai(fs,st,mid);
	build_ai(fs+1,mid+1,dr);

	stotal[poz]=stotal[fs]+stotal[fs+1];
	smaxleft[poz]=max(smaxleft[fs], stotal[fs]+smaxleft[fs+1]);
	smaxright[poz]=max(stotal[fs+1]+smaxright[fs], smaxright[fs+1]);
	smax[poz]=max(smaxright[fs]+smaxleft[fs+1], max(smax[fs], smax[fs+1]));
}

void query_ai(int poz, int st, int dr) {
	if(st>y || dr<x) return;
	if(st>=x && dr<=y) {
		if(sum<0) sum=0;

		res=max(res,max(sum+smaxleft[poz], smax[poz]));
		sum=max(sum+stotal[poz], smaxright[poz]);
		return;
	}

	int fs=poz<<1, mid=(st+dr)>>1;
	query_ai(fs,st,mid);
	query_ai(fs+1,mid+1,dr);
}

int main() {
	int n,i,m;

	fin>>n>>m;

	for(i=1;i<=n;++i) fin>>v[i];
	build_ai(1,1,n);

	while(m--) {
		fin>>x>>y;

		res=-1LL*INF*INF;
		sum=0;
		query_ai(1,1,n);
		fout<<res<<'\n';
	}

	return 0;
}