#include <bits/stdc++.h>
#define maxim 100008


using namespace std;


ifstream f("sequencequery.in");
ofstream g ("sequencequery.out");

const long long  inf=1e10;

struct
{
    long long  max,st,dr,sum;
} tree[maxim<<2];

int n,v[maxim],m;

long long maxi ( long long a ,  long long b, long long c)
{
    return max(a,max(b,c));
}


void create(int nod, int i, int  j)
{
    if (i == j)
        tree[nod]={v[i],v[i],v[i],v[i]};
    else
    {
        int mij=(i+j)/2;
        create(nod*2, i, mij);
        create(nod*2+1, mij+1, j);

        tree[nod].sum = tree[nod*2].sum + tree[nod*2+1].sum;
        tree[nod].max = maxi( tree[nod*2].max, tree[nod*2+1].max, tree[nod*2].dr + tree[nod*2+1].st );
        tree[nod].st  = max( tree[nod*2].st, tree[nod*2].sum + tree[nod*2+1].st);
        tree[nod].dr  = max (tree[nod*2+1].dr , tree[nod*2+1].sum + tree[nod*2].dr);
    }
}


long long  ans,dreapta;

void query(int nod, int i, int j, const int a, const int b)
{
    if (a <= i && b>= j) //inclus complet
    {
       ans=maxi(ans,tree[nod].max,dreapta+tree[nod].st);
       dreapta=max(tree[nod].dr, dreapta+tree[nod].sum);
    }
    else
    {
        int mij=(i+j)/2;
        if (a <= mij)
            query(nod*2, i, mij, a, b);
        if (b > mij)
            query(nod*2+1, mij+1, j, a, b);

    }
}

int main()
{


    f>>n>>m;
    for (int i=1 ; i<=n ; i++)
        f>>v[i];
    create(1,1,n);
    while(m--)
    {
        int a,b;
        f>>a>>b;
        ans=-inf;
        dreapta=0;
        query(1, 1, n, a, b);
        g<<ans<<'\n';
    }


}