#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("test.in");
ofstream g("sequencequery.out");

struct arb{
    int prefix, s_tot, sufix;
}tree[100005],aux;

int n, m, x, stq, drq;

void adaugare_tree(int st, int dr, int ind, int val, int i)
{
    if (st==dr)
    {
        tree[ind].prefix=tree[ind].s_tot=tree[ind].sufix=val;
        return;
    }
    int mij=(st+dr)/2;
    if (mij<i)
        adaugare_tree(mij+1,dr,ind*2+1,val,i);
    else
        adaugare_tree(st,mij,ind*2,val,i);
}

void formare_tree(int st, int dr, int ind)
{
    if (st==dr)
        return;
    int mij=(st+dr)/2;
    formare_tree(mij+1,dr,ind*2+1);
    formare_tree(st,mij,ind*2);
    tree[ind].s_tot=tree[ind*2].s_tot+tree[ind*2+1].s_tot;
    tree[ind].prefix=max(tree[ind*2].prefix,tree[ind*2].s_tot+tree[ind*2+1].prefix);
    tree[ind].sufix=max(tree[ind*2+1].sufix,tree[ind*2+1].s_tot+tree[ind*2].sufix);
}

arb query(int st, int dr, int ind, int stq, int drq)
{
    if (st>drq || dr<stq)
        {
            arb a;
            a.prefix=a.sufix=a.s_tot=-999999;
            return a;
        }
    if (st>=stq && dr<=drq)
        return tree[ind];
    int mij=(st+dr)/2;
    arb a = query(st,mij,ind*2,stq,drq);
    arb b= query(mij+1,dr,ind*2+1,stq,drq);
    if (ind==1)
    {
        g << max(a.sufix,max(a.prefix,max(a.sufix+b.prefix,max(b.sufix,b.prefix))));
        g << '\n';
    }
    arb r;
    r.s_tot=a.s_tot+b.s_tot;
    r.prefix=max(a.prefix,a.s_tot+b.prefix);
    r.sufix=max(b.sufix,a.sufix+b.s_tot);
    return r;
}

arb gasire(int st, int dr, int ind, int cautat)
{
    if (st==dr)
        return tree[ind];
    int mij=(st+dr)/2;
    if (mij<cautat)
        return gasire(mij+1,dr,ind*2+1,cautat);
    return gasire(st,mij,ind*2,cautat);
}

int main()
{
    fin >> n >> m;
    for (int i=1; i<=n; ++i)
    {
        fin >> x;
        adaugare_tree(1,n,1,x, i);
    }
    formare_tree(1,n,1);
    for (int i=1; i<=m; ++i)
    {
        fin >> stq >> drq;
        aux.prefix=aux.sufix=aux.s_tot=0;
        if (stq==drq)
            g<<gasire(1,n,1,stq).s_tot << '\n';
        else
            query(1,n,1,stq,drq);
    }
    return 0;
}