#include <fstream>
using namespace std;

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

const int N_MAX = 100000;
int N, M;
struct Int
{
    long long max_sum, l_sum, r_sum, total_sum;
}Tree[4*N_MAX];

Int join(Int a, Int b)
{
    Int ans;
    ans.max_sum = max(max(a.max_sum, b.max_sum), a.r_sum+b.l_sum);
    ans.l_sum = max(a.l_sum, a.total_sum+b.l_sum);
    ans.r_sum = max(a.r_sum + b.total_sum, b.r_sum);
    ans.total_sum = a.total_sum+b.total_sum;
    return ans;
}

void update(int node, int l, int r, int pos, int val)
{
    if(l == r)
    {
        Tree[node] = {val, val, val, val};
        return;
    }

    int mid = (l + r)/2;
    if(pos <= mid)
        update(2*node, l, mid, pos, val);
    else
        update(2*node+1, mid+1, r, pos, val);
    Tree[node] = join(Tree[2*node], Tree[2*node+1]);
}

Int query(int node, int nodeL, int nodeR, int l, int r)
{
    if(nodeL == l && nodeR == r)
        return Tree[node];

    int mid = (nodeL + nodeR)/2;
    if(r <= mid)
        return query(2*node, nodeL, mid, l, r);
    if(mid+1 <= l)
        return query(2*node+1, mid+1, nodeR, l, r);
    return join(query(2*node, nodeL, mid, l, mid), query(2*node+1, mid+1, nodeR, mid+1, r));
}

int main()
{
    in >> N >> M;
    for(int i = 1; i <= N; i++)
    {
        int x;
        in >> x;
        update(1, 1, N, i, x);
    }
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        in >> x >> y;
        out << query(1, 1, N, x, y).max_sum << "\n";
    }
    return 0;
}