#include<bits/stdc++.h>
using namespace std;

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

const int N = 1e5;

int v[N + 1];

int q, n;


struct tree
{
    int sum;
    int pref_scmax;
    int suff_scmax;
    int scmax;
};

tree A[4 * N + 1];

tree combine(tree left, tree right)
{
    tree curent;
    curent.sum = left.sum + right.sum;
    curent.pref_scmax = max(left.pref_scmax, left.sum + right.pref_scmax);
    curent.suff_scmax = max(right.suff_scmax, right.sum + left.suff_scmax);
    curent.scmax = max(left.suff_scmax + right.pref_scmax, max(left.scmax, right.scmax));
    return curent;
}

tree query(int node, int left, int right, int query_left, int query_right)
{
    if (query_left <= left and right <= query_right)
    {
        return A[node];
    }
    else
    {
        int mid = (left + right) / 2;
        if (query_right <= mid)
            return query(node * 2, left, mid, query_left, query_right);
        if (mid + 1 <= query_left)
            return query(node * 2 + 1, mid + 1, right, query_left, query_right);
        tree left_node = query(node * 2, left, mid, query_left, query_right);
        tree right_node = query(node * 2 + 1, mid + 1, right, query_left, query_right);
        return combine(left_node, right_node);
    }
}

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        A[nod].sum = v[st];
        A[nod].pref_scmax = v[st];
        A[nod].suff_scmax = v[st];
        A[nod].scmax = v[st];
    }
    else
    {
        int mid = (st + dr) / 2;
        build(nod * 2, st, mid);
        build(nod * 2 + 1, mid + 1, dr);
        A[nod] = combine(A[nod * 2], A[nod * 2 + 1]);

    }
}

signed main()
{
    in >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        in >> v[i];
    }
    build(1, 1, n);
    while(q--)
    {
        int x, y;
        in >> x >> y;
        out << query(1, 1, n, x, y).scmax << '\n';
    }
    return 0;
}