#include <fstream>

#define maxn 100001
#define ll long long
#define inf 1<<30

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

ll v[maxn];
int n,l,r,m;
ll s[4*maxn];

struct arb
{
    ll x,l,r;
}ar[4*maxn];


/*arb query (int node, int left, int right)
{
    if (l <= left && right >= r)
    {

    }
}*/

void create_arb (int node, int left, int right)
{
    if (left!=right)
    {
        int mid = (left+right)/2;
        create_arb (node<<1,left,mid);
        create_arb ((node<<1)+1,mid+1,right);
    }

    ll maxv = -inf,sum = -inf,ssum=0;

    for (int i=left; i<=right; ++i)
    {
        if (sum < 0)
        {
            sum = v[i];
        }
        else sum += v[i];

        if (sum > maxv)
        {
            maxv = sum;
        }

        ssum += v[i];
    }

    ar[node].l = sum;
    s[node] = ssum;

    sum = -inf;

    for (int i=right; i>=left; --i)
    {
        if (sum < 0)
        {
            sum = v[i];
        }
        else sum += v[i];

        if (sum > maxv)
        {
            maxv = sum;
        }
    }

    ar[node].r = sum;

    ar[node].x = maxv;
}

arb query (int node, int left, int right)
{
    if (left >= l && r >= right)
    {
        return ar[node];
    }

    int mid = (left+right)/2;

    arb x,y;
    x.x = -inf, x.l = -inf, x.r=-inf;
    y.x =-inf,y.l=-inf,y.r=-inf;

    if (l <= mid)
        x = query (node<<1,left,mid);
    if (r > mid)
        y = query ((node<<1)+1,mid+1,right);

    arb ans;
    ans.r = max (x.r,s[node<<1]+y.r);
    ans.l = max (y.l,s[(node<<1)+1]+x.l);
    ans.x = max (x.l+y.r,max(x.x,y.x));
    return ans;
}

int main()
{
    fin>>n>>m;

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

    create_arb (1,1,n);

    for (int i=1; i<=m; ++i)
    {
        fin>>l>>r;
        fout<<(query(1,1,n)).x<<"\n";
    }
}