#include<cstdio>
    #include<iostream>
    using namespace std;
    #define NMAX 100001
    #define LL long long
    int N , M  , v[NMAX] ;
    LL S[4*NMAX] , L[4*NMAX] , R[4*NMAX] , C[4*NMAX];
    struct ans
    {
        LL s,l,r,c;
    };

    void build(int n , int  l , int r );
    ans query(int n , int l , int r , int a , int b);

    int main()
    {
        int x , y;
        freopen("sequencequery.in" , "r" , stdin );
        freopen("sequencequery.out" , "w" , stdout );
        scanf("%d%d" , &N , &M);
        for(int i = 1 ; i<= N ; ++i )
            scanf("%d" , &v[i]);
        build(1,1,N);
        for(int i = 1 ; i<= M ; ++i )
        {
            scanf("%d%d" , &x , &y );
            printf("%lld\n" , query(1,1,N,x,y).s);
        }
        return 0;
    }

    void build(int n , int l  ,int r)
    {
        if(l == r)
            S[n] = L[n] = R[n] = C[n] = v[l];
        else
        {
            int m = (l+r)/2;
            build(2*n,l,m);
            build(2*n+1,m+1,r);
            S[n] = max(S[2*n],S[2*n+1]);
            S[n] = max(S[n],R[2*n]+L[2*n+1]);
            L[n] = L[2*n];
            L[n] = max(L[n],C[2*n]+L[2*n+1]);
            R[n] = R[2*n+1];
            R[n] = max(R[n],C[2*n+1] + R[2*n]);
            C[n] = C[2*n]+C[2*n+1];
        }
    }

    ans query(int n , int  l ,int r , int a , int b)
    {
        if(a <= l && b >= r)
        {
            ans a;
            a.s = S[n]; a.l = L[n] ; a.r = R[n]; a.c = C[n];
            return a;
            }
        else
        {
            int m = (l+r)/2;
            ans a1,a2;
            if(a <= m)
                a1 = query(2*n,l,m,a,b);
            if(b > m)
            {
                a2 = query(2*n+1,m+1,r,a,b);
                if(a <= m){
                a1.s = max(a1.s,a2.s);
                a1.s = max(a1.s,a1.r+a2.l);
                a1.l = max(a1.l,a1.c+a2.l);
                a1.r = max(a2.r,a2.c+a1.r);
                a1.c +=a2.c;}
                else return a2;
            }
            return a1;
        }
    }