#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5;

int v[N + 1];

int n, q;

struct tree_node
{
    long long sum;
    long long pref_scmax;
    long long suff_scmax;
    long long scmax;
};

tree_node A[4 * N + 1];

tree_node update_node(tree_node left_node, tree_node right_node)
{
    tree_node current_node;
    current_node.sum = left_node.sum + right_node.sum;
    current_node.pref_scmax = max(left_node.pref_scmax, left_node.sum + right_node.scmax);
    current_node.suff_scmax = max(right_node.suff_scmax, right_node.sum + left_node.suff_scmax);
    current_node.scmax = max((left_node.suff_scmax + right_node.pref_scmax), max(left_node.scmax, right_node.scmax));
    return current_node;
}

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

tree_node query(int nod, int st, int dr, int a, int b)
{
    if(a <= st && dr <= b)
    {
        return A[nod];
    }
    else{
        int mij = (st + dr) / 2;
        if(a <= mij)
            return query(2 * nod, st, mij, a, b);
        if(b >= mij + 1)
            return query(2 * nod + 1, mij + 1, dr, a, b);
        A[nod] = update_node(A[nod * 2], A[2 * nod + 1]);
    }
}

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