#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int NMAX=100005;

///smax-valoarea subsecventei de suma maxima in intervalul dat de nodul arborelui de intervale
///mx-cea mai mare valoare pentru sum[i] in intervalul dat de nodul arborelui de intervale
///mn-cea mai mica valoare pentru sum[i-1] in intervalul dat de nodul arborelui de intervale
int N, M;
ll sum[NMAX], minPref;
struct node{
    ll smax, mx, mn;
}seg[4*NMAX];

void build(int nod, int st, int dr){
    if(st==dr){
        seg[nod]={sum[st]-sum[st-1],sum[st],sum[st-1]};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    seg[nod].mx=max(seg[nod*2].mx,seg[nod*2+1].mx);
    seg[nod].mn=min(seg[nod*2].mn,seg[nod*2+1].mn);
    seg[nod].smax=max(max(seg[nod*2].smax,seg[nod*2+1].smax),seg[nod*2+1].mx-seg[nod*2].mn);
}

ll query(int nod, int st, int dr, int p1, int p2){
    if(st>=p1 and dr<=p2){
        ll sol=seg[nod].smax;
        if(minPref!=LLONG_MAX)
            sol=max(sol,seg[nod].mx-minPref);
        minPref=min(minPref,seg[nod].mn);
        return sol;
    }
    int mij=(st+dr)/2;
    if(p1<=mij and p2>mij)
        return max(query(nod*2+1,mij+1,dr,p1,p2),query(nod*2,st,mij,p1,p2));
    if(p1<=mij)
        return query(nod*2,st,mij,p1,p2);
    return query(nod*2+1,mij+1,dr,p1,p2);
}

int main()
{
    fin>>N>>M;
    for(int i=1;i<=N;i++){
        fin>>sum[i];
        sum[i]+=sum[i-1];
    }
    build(1,1,N);

    int x, y;
    while(M--){
        fin>>x>>y;
        minPref=LLONG_MAX;
        fout<<query(1,1,N,x,y)<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}