#include <bits/stdc++.h>
#define MAX_N 100001
#define INIT_MID int mid = (st + dr) /2
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct tree_node{
    long long sum;
    long long prefix_smax;
    long long sufix_smax;
    long long smax;
} aint[MAX_N];
int v[MAX_N];
int nr_elem, nr_query;

tree_node update_node(tree_node node_st, tree_node node_dr){
    tree_node curr_node;
    curr_node.sum = node_st.sum + node_dr.sum;
    curr_node.prefix_smax = max(node_st.prefix_smax, node_st.sum + node_dr.prefix_smax);
    curr_node.sufix_smax = max(node_dr.sufix_smax,node_dr.sum + node_st.sufix_smax);
    curr_node.smax = max(node_st.sufix_smax + node_dr.prefix_smax, max(node_st.smax, node_dr.smax));
    return curr_node;
}
void build(int node, int st, int dr){
    if(st == dr)
        aint[node] = {v[st],v[st],v[st],v[st]};
    else{
        INIT_MID;
        build(node*2, st, mid);
        build(node*2+1, mid + 1, dr);
        aint[node] = update_node(aint[node*2], aint[node*2+1]);
    }
    return;
}
tree_node query(int node, int st, int dr, int qSt, int qDr){
    if(qSt <= st && dr <=qDr)
        return aint[node];
    else{
        INIT_MID;
        if(qDr <= mid)
            return query(node*2, st, mid, qSt, qDr);
        if(mid + 1 <= qSt)
            return query(node*2+1, mid+1 , dr, qSt, qDr);
        return update_node(query(node*2, st, mid, qSt, qDr),
                           query(node*2+1, mid+1, dr, qSt, qDr)
                           );
    }
}

int main()
{
    fin>>nr_elem>>nr_query;
    for(int i = 1; i<=nr_elem; i++)
        fin>>v[i];
    build(1,1,nr_elem);
    int st,dr;
    for(int i = 1; i<=nr_query; i++){
        fin>>st>>dr;
        fout<<query(1, 1, nr_elem, st, dr).smax<<'\n';

    }
    return 0;
}