#include <bits/stdc++.h>

#define FastIo() ios_base::sync_with_stdio(false), fin.tie(nullptr),fout.tie(nullptr);
#define ll int64_t
#define pii pair<int,int>
#define pipii pair<int,pair<int,int>>
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
//
//#define fin cin
//#define fout cout

int n, m, x, y;
const int NMAX = 100001;
ll v[NMAX];

struct tree_node {
    ll sum, pref_scmax, sufix_scmax,scmax;
};
vector<tree_node> tree(4 * NMAX);

tree_node update_node(tree_node l_node, tree_node r_node){
    tree_node curr_node;
    curr_node.sum = l_node.sum + r_node.sum;

    curr_node.pref_scmax = max(l_node.pref_scmax,  l_node.sum + r_node.pref_scmax);
    curr_node.sufix_scmax = max(r_node.sufix_scmax, r_node.sum + l_node.sufix_scmax);

    curr_node.scmax = max(l_node.sufix_scmax + r_node.pref_scmax,max(l_node.scmax, r_node.scmax));
    return curr_node;
}

void buildTree(int node = 1, int l = 1, int r = n) {
    if (l == r) {
        tree[node] = { v[l], v[l], v[l], v[l]};
    } else {
        int m = (l + r) / 2;
        buildTree(2 * node, l, m);
        buildTree(2 * node + 1, m + 1, r);
        tree[node] = update_node(tree[2*node], tree[2*node+1]);
    }
}

tree_node query(int node, int l, int r, int queryL, int queryR) {
    if (queryL <= l && r <= queryR) {
        return tree[node];
    } else {
        int m = (l + r) / 2;

        if (queryR <= m) return query(2 * node, l, m, queryL, queryR);
        if (m < queryL) return query(2 * node + 1, m + 1, r, queryL, queryR);
        tree_node query0 = query(2 * node, l, m, queryL, queryR);
        tree_node query1 = query(2 * node + 1, m + 1, r, queryL, queryR);
        tree_node crr;
        return {0,0,0,max(query0.sufix_scmax + query1.pref_scmax, max(query0.scmax,query1.scmax))};
    }
}


int main() {

    fin >> n >> m;

    for (int i = 1; i <= n; i++) fin >> v[i];
    buildTree();
    for(int i=1;i<=m;i++){
        fin>>x>>y;
        fout<<query(1,1,n,x,y).scmax<<'\n';
    }
    return 0;
}