#define NMAX 100005
#include <fstream>
#include <vector>
using namespace std;

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

typedef long long int lli;

int n, m, x, y;
int sir[NMAX];


class tree
{
    private:
        struct nod
        {
            lli sm_st, sm_dr, sm_all, sm_max;


            nod operator+(nod b)
            {
                nod rez;
                rez.sm_all = sm_all + b.sm_all;
                rez.sm_max = max(sm_dr + b.sm_st, max(sm_max, b.sm_max));
                rez.sm_st = max(sm_st, sm_all + b.sm_st);
                rez.sm_dr = max(b.sm_dr, b.sm_all + sm_dr);
                return rez;
            }

        };
        vector<nod> aib;

        void recursive_form(int left, int right, int index)
        {
            if(left == right)
            {
                aib[index].sm_st = sir[left];
                aib[index].sm_dr = sir[left];
                aib[index].sm_all = sir[left];
                aib[index].sm_max = sir[left];
                return;
            }
            int mid = (left + right)/2;
            recursive_form(left, mid, 2*index);
            recursive_form(mid+1, right, 2*index+1);

            aib[index] = aib[2*index] + aib[2*index + 1];
        }

        nod find_sum(int index, int left, int right, int a, int b)
        {
            if(a <= left && right <= b)
                return aib[index];
            nod maxs, maxdr;
            int mid = (left + right)/2;
            if(a >= mid+1)
            {
                maxdr = find_sum(2*index+1, mid+1, right, a, b);
                return maxdr;
            }
            else if(b <= mid)
            {
                maxs = find_sum(2*index, left, mid, a, b);
                return maxs;
            }
            else{
                maxs = find_sum(2*index, left, mid, a, b);
                maxdr = find_sum(2*index+1, mid+1, right, a, b);
            }
            return maxs + maxdr;
        }




    public:
        lli querry(int a, int b)
        {
            return find_sum(1, 1, n, a, b).sm_max;
        }

        void form()
        {
            aib.resize(4*n);
            recursive_form(1, n, 1);
        }


}aib;


int main()
{
    f>>n>>m;
    for(int i=1; i<=n; ++i)
        f>>sir[i];
    aib.form();
    for(int i=1; i<=m; ++i)
    {
        f>>x>>y;
        g<<aib.querry(x, y)<<"\n";
    }
    return 0;
}