#include <iostream>
#include <fstream>

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

const int N = 100000;
long long arr[N+1];

struct tree_node{
    long long sum;
    long long smax;
    long long pref_smax;
    long long suff_smax;
}segment_tree[4*N+1];

tree_node update_node(tree_node left, tree_node right)
{
    tree_node current_node;
    current_node.sum = left.sum + right.sum;
    current_node.pref_smax = max(right.pref_smax, right.sum + left.pref_smax);
    current_node.suff_smax = max(left.suff_smax, left.sum + right.suff_smax);
    current_node.smax = max(left.pref_smax+right.suff_smax, (left.smax, right.smax));
    return current_node;
}

void build(int node, int left, int right)
{
    if(left == right)
        segment_tree[node].sum = segment_tree[node].smax = segment_tree[node].pref_smax = segment_tree[node].suff_smax = arr[left];
    else
    {
        int m = (left + right) / 2;
        build(node*2, left, m);
        build(node*2+1, m+1, right);
        segment_tree[node] = update_node(segment_tree[node*2], segment_tree[node*2+1]);
    }
}

tree_node query(int node, int left, int right, int q_left, int q_right)
{
    if(q_left <= left && right <= q_right)
        return segment_tree[node];
    else
    {
        int m = (left + right) / 2;
        if(q_right <= m)
            return query(node*2, left, m, q_left, q_right);
        if(m + 1 <= q_left)
            return query(node*2+1, m+1, right, q_left, q_right);
        return update_node(query(node*2, left, m, q_left, q_right), query(node*2+1, m+1, right, q_left, q_right));
    }
}

int main()
{
    int n, m, x, y;
    fin >> n >> m;
    for(int i = 1; i <= n; ++i)
        fin >> arr[i];
    build(1, 1, n);
    while(m--)
    {
        fin >> x >> y;
        fout << query(1, 1, n, x, y).smax << '\n';
    }
    return 0;
}