/*
    Programmer : Alexandru Olteanu
*/
#include<bits/stdc++.h>
using namespace std;
// GCC Optimizations
// #pragma GCC optimize("Ofast");
// #pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt")
// #pragma GCC target("abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize(3)
// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse")
// #pragma GCC optimize("-fgcse-lm")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-ftree-pre")
// #pragma GCC optimize("-ftree-vrp")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("unroll-loops")
// Useful
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define FastEverything  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define HighPrecision cout<<fixed<<setprecision(17);
typedef long long ll;
typedef pair<int,int> pii;
ll const mod=1000000007LL;
ll const mod2 = 100000000LL;
ll const md=998244353LL;
ll mypowr(ll a,ll b, ll mod1) {ll res=1;if(b<0)b=0;a%=mod1; assert(b>=0);
for(;b;b>>=1){if(b&1)res=res*a%mod1;a=a*a%mod1;}return res;}
ll mypow(ll a,ll b) {ll res=1;if(b<0)b=0;assert(b>=0);
for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
 
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
#define cin in
#define cout out

const ll infll = 9e18;
const int inf = 2e9;
const ll maxn = 1e5 + 2;

struct arbore {
	int s,max,st,dr;
};
int n,m;
int v[maxn];
arbore a[1<<18];
long long suma,maxim;

void build(int nod, int st, int dr)
{
	int left=nod<<1;
	int right=left|1;
	int m=(st+dr)>>1;
	if(st==dr)
	{
		a[nod].s=a[nod].max=a[nod].st=a[nod].dr=v[st];
		return;
	}
	build(left,st,m);
	build(right,m+1,dr);
	a[nod].s=a[left].s+a[right].s;
	a[nod].max=max(max(a[left].max,a[right].max),a[left].dr+a[right].st);
	a[nod].st=max(a[left].st,a[left].s+a[right].st);
	a[nod].dr=max(a[right].dr,a[right].s+a[left].dr);
}
 
void query(int nod, int st, int dr, int left, int right)
{
	long long rez=0;
	if(left<=st && dr<=right)
	{
		rez=a[nod].max;
		if(suma+a[nod].st>rez)
			rez=suma+a[nod].st;
		if(suma+a[nod].s>a[nod].dr)
			suma+=a[nod].s;
		else
			suma=a[nod].dr;
		if(rez>maxim)
			maxim=rez;
		return;
	}
	int m=(st+dr)>>1;
	if(left<=m)
		query(nod<<1,st,m,left,right);
	if(m<right)
		query((nod<<1)|1,m+1,dr,left,right);
}


int main()
{
    FastEverything
    HighPrecision
 
    int test = 1;
    // cin >> test;
    for (int tt = 1; tt <= test; ++tt) { 
        cin >> n >> m;
        int i,st,dr;
        for(i = 1;i <= n; ++i) {
            cin >> v[i];
        }
        build(1, 1, n);
        for(i=1;i<=m;i++)
        {
            cin >> st >> dr;
            suma=0;
            maxim= -infll;
            query(1,1,n,st,dr);
            cout << maxim << '\n';
        }
    }
 
    return 0;
}