#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int MAX=1e5;
int n,i,q,v[MAX+5],l,r;

struct node{
long long sum,suffix,preffix,smax;}A[4*MAX+5];

node get(node leftchild, node rightchild)
{
    node father;
    father.sum=leftchild.sum+rightchild.sum;
    father.preffix=max(leftchild.preffix,leftchild.sum+rightchild.preffix);
    father.suffix=max(rightchild.suffix,rightchild.sum+leftchild.suffix);
    father.smax=max({leftchild.smax,rightchild.smax,leftchild.suffix+rightchild.preffix});
    return father;
}



void build(int nod ,int st ,int dr)
{
    if (st==dr)
    {
            A[nod].sum=v[st];
            A[nod].preffix=v[st];
            A[nod].suffix=v[st];
            A[nod].smax=v[st];
    }
    else
    {
        int mij=(st+dr)>>1;

        build(2*nod,st,mij);
        build(2*nod+1,mij+1,dr);
        A[nod]=get(A[2*nod],A[2*nod+1]);
    }
}

node query(int nod ,int st ,int dr ,int a, int b)
{
    if (a<=st && dr<=b)
        return A[nod];
    else
    {
        int mij=(st+dr)>>1;

        if (b<=mij)
            return query(2*nod,st,mij,a,b); // intervalul cautat apare doar in fiul stang

        if (a>mij)
            return query(2*nod+1,mij+1,dr,a,b); // intervalul cautat apare doar in fiul drept

        node leftchild=query(2*nod,st,mij,a,b);
        node rightchild=query(2*nod+1,mij+1,dr,a,b);
        return get(leftchild,rightchild);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);

    fin>>n>>q;

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

    build(1,1,n);

    while (q--)
    {
        fin>>l>>r;
        fout<<query(1,1,n,l,r).smax<<"\n";
    }


    return 0;
}