///Alexandru Morus
#include <bits/stdc++.h>

using namespace std;
ifstream in("sequencequery.in");
ofstream out ("sequencequery.out");
int v[200080],af;
#define int long long
struct Node
{
    int sum_max;
    int sum_max_le;
    int sum_max_ri;
    int total_sum;
}aint[800008];
Node combine(Node a, Node b)
{
    Node af;
    af.total_sum = a.total_sum + b.total_sum;
    af.sum_max_le = max(a.sum_max_le, a.total_sum + b.sum_max_le);
    af.sum_max_ri = max(b.sum_max_ri,b.total_sum + a.sum_max_ri);
    af.sum_max = max(max(a.sum_max,b.sum_max),max(max(af.sum_max_le,af.sum_max_ri),a.sum_max_ri + b.sum_max_le));
    return af;
}
void build(int node, int l, int r)
{
    if(l == r)
    {
        aint[node].sum_max = v[l];
        aint[node].sum_max_le = v[l];
        aint[node].sum_max_ri = v[l];
        aint[node].total_sum = v[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node , l ,mid);
    build(2 * node + 1, mid + 1, r);
    aint[node] = combine(aint[2 * node], aint[2 * node + 1]);
}
void update(int node, int le, int ri, int pos, int val)
{
    if(le == ri)
    {
        aint[node].sum_max = val;
        aint[node].sum_max_le = val;
        aint[node].sum_max_ri = val;
        aint[node].total_sum = val;
        return;
    }
    int mid = (le + ri) / 2;
    if(pos <= mid)
    {
        update(2 * node,le,mid,pos,val);
    }
    else
    {
        update(2 * node + 1,mid + 1, ri,pos,val);
    }
    aint[node] = combine(aint[2 * node], aint[2 * node + 1]);
}
Node query(int node, int le, int ri, int a, int b)
{
    if(a <= le && ri <= b)
    {
        return aint[node];
    }
    int mid = (le + ri) / 2;
    if(b <= mid)
    {
         return query(2 * node,le,mid,a,b);
    }
    if(a > mid)
    {
         return query(2 * node + 1,mid + 1,ri,a,b);
    }
    Node left = query(2 * node,le,mid,a,b);
    Node right = query(2 * node + 1,mid + 1,ri,a,b);
    return combine(left,right);
}
signed main()
{
    int i,a,b,n,m,c;
    in >> n >> m;
    for(i = 1; i <= n; i ++)
    {
        in >> v[i];
    }
    build(1,1,n);
    //in ;
    for(i = 1; i <= m; i ++)
    {
        in >> a >> b;
        //if(c == 0)
        {
            //update(1,1,n,a,b);
        }
        //else
        {
            out << query(1,1,n,a,b).sum_max << '\n';
        }
    }
    return 0;
}