#include <bits/stdc++.h>
#define MAX_N (100000)
 
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m,aux;
struct Arb{long long S,D,C,Sum;}Ar[MAX_N*4];
void build(int,int,int);
void update(int,int,int,int,int);
Arb query(int,int,int,int,int);
 
int main()
{
    int v1,v2;
    fin>>n>>m;
    build(1, 1, n);
    for(int i=1;i<=m;i+=1)
    {
        fin>>v1>>v2;
        fout<<query(1,1,n,v1,v2).C<<'\n';
    }
    return 0;
}
 
void build(int n, int l, int r)
{
    if (l == r)
    {
        int aux;
        fin>>aux;
        Ar[n].S = Ar[n].D = Ar[n].C = aux;
        Ar[n].Sum = aux;
    }
    else
    {
        int leftNode=n<<1,rightNode=n<<1|1,middle=(l+r)>>1;
 
        build(leftNode, l, middle);
        build(rightNode, middle+1, r);
 
        Ar[n].C = max(max(Ar[leftNode].C, Ar[rightNode].C), Ar[leftNode].D+Ar[rightNode].S);
        Ar[n].D = max(Ar[leftNode].D+Ar[rightNode].Sum, Ar[rightNode].D);
        Ar[n].S = max(Ar[leftNode].S, Ar[leftNode].Sum + Ar[rightNode].S );
        Ar[n].Sum = Ar[leftNode].Sum+Ar[rightNode].Sum;
    }
}
 
Arb query(int n, int l, int r, int a, int b)
{
    if (a <= l && r <= b) return Ar[n];
    else
    {
        int leftNode=n<<1,rightNode=n<<1|1,middle=(l+r)>>1;
 
        if(b<=middle) return query(leftNode,l,middle,a,b);
        else if(a>middle) return query(rightNode,middle+1,r,a,b);
        else
        {
            Arb leftInterval = query(leftNode,l,middle,a,b);
            Arb rightInterval = query(rightNode,middle+1,r,a,b);
            Arb aux;
            aux.C = max(max(leftInterval.C, rightInterval.C), leftInterval.D+rightInterval.S);
            aux.S = max(leftInterval.Sum+rightInterval.S, leftInterval.S);
            aux.D = max(rightInterval.Sum+leftInterval.D, rightInterval.D);
            aux.Sum = leftInterval.Sum+rightInterval.Sum;
 
            return aux;
        }
    }
}