#include <cstdio>
#include <vector>
#include <stdarg.h>
#include <cassert>
using namespace std;

#define smax first.first
#define drmax second.second
#define stmax second.first
#define sp first.second

class SegmentTree
{
public:
    SegmentTree(int n)
    {
        this->n=n;
        arb.resize(n*4);
        // assert(get_max (3, 4, 5, 6) == 6) ;
    }
    void Update(int poz,int val)
    {
        update(1,1,n,poz,val);
    }
    long long sol(int a,int b)
    {
        long long sum = 0 ;
        long long best = - (1LL << 60) ;
        query(1,1,n,a,b,sum,best);
        return max (1LL * sum, 1LL * best);
    }
private:
    long long get_max (int num, ...) {
        // printf ("%d**\n", num) ;
        va_list v ;
        long long sol = - (1LL << 62) ;
        va_start (v, num) ;
        for (int i = 0 ; i < num ; ++ i) {
            long long value = va_arg(v, long long) ;
            // printf ("%lld\n", value) ;
            sol = max (sol , value) ;
        } 
        va_end (v) ;
        return sol ;
    }
    int n;

    vector < pair <pair<long long, long long>, pair<long long, long long>> >arb;
    void update(int nod,int st,int dr,int poz,int val)
    {
        if(st==dr)
        {
            arb[nod] = {{1LL * val,1LL * val}, {1LL * val,1LL * val}} ;
            return ;
        }
        int mij = (st + dr) >> 1;
        if (poz <= mij) {
            update (nod * 2, st, mij, poz, val) ;
        }
        else {
            update (nod * 2 + 1, mij + 1, dr, poz, val) ;
        }
        arb [nod].sp = arb [nod * 2].sp + arb [nod * 2 + 1].sp ;
        arb [nod].stmax = get_max (2, arb[nod * 2].stmax, arb [nod * 2 + 1].stmax + arb [nod * 2].sp) ;
        arb [nod].drmax = get_max (2, arb[nod * 2 + 1].drmax, arb [nod * 2].drmax + arb [nod * 2 + 1].sp) ;
        arb [nod].smax = get_max (6, arb [nod].sp, arb [nod].stmax, arb [nod].drmax, arb [nod * 2].drmax + arb [nod * 2 + 1].stmax,
            arb [nod * 2].smax, arb [nod * 2 + 1].smax) ;
    }
    void query(int nod,int st,int dr,int a,int b, long long &partial_sum, long long &best)
    {
        if(a<=st && dr<=b){
            if (partial_sum < 0) {
                partial_sum = 0 ;
            }
            best = get_max (3, best, partial_sum + arb [nod].stmax, arb [nod].smax) ;
            partial_sum = get_max (2, partial_sum + arb [nod].sp, arb [nod].drmax) ;
            return ;
        }      
        int mij=(st+dr)>>1;
        if(a<=mij)
            query(nod<<1,st,mij,a,b, partial_sum, best);
        if(b>mij)
            query((nod<<1)+1,mij+1,dr,a,b, partial_sum, best);
    }
};
int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int n,m;
    scanf("%d",&n); scanf("%d",&m);
    SegmentTree *A= new SegmentTree(n);
    for(int i=1; i<=n; ++i)
    {
        int x;
        scanf("%d",&x);
        A->Update(i,x);
    }
    for(int i=1; i<=m; ++i)
    {
        int b,c;
        scanf("%d%d",&b,&c);
        printf ("%lld\n", A->sol(b,c));
    }
    return 0;
}