#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = a; i <= b; i++)
#define pb push_back
#define ll long long
#define ln '\n'
#define cin f
#define cout g
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

int n, q;

struct tree_node{
        ll sum, pref, suff, scmax;
};

int a[100001];
tree_node segment_tree[400001];

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 = max(left_node.pref, left_node.sum + right_node.pref);

        current_node.suff = max(right_node.suff, right_node.sum + left_node.suff);

        current_node.scmax = max(left_node.suff + right_node.pref, max(left_node.scmax, right_node.scmax));

        return current_node;
}

void build(int node, int left, int right){
        if(left == right){
                segment_tree[node].sum = a[left];
                segment_tree[node].pref = a[left];
                segment_tree[node].suff = a[left];
                segment_tree[node].scmax = a[left];
        }
        else{
                int middle = (left + right) / 2;

                build(node * 2, left, middle);
                build(node * 2 + 1, middle + 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 query_left, int query_right){
        if(query_left <= left && right <= query_right){
                return segment_tree[node];
        }
        else{
                int middle = (left + right) / 2;
                if(query_right <= middle)
                        return query(2 * node, left, middle, query_left, query_right);
                
                if(query_left > middle)
                        return query(2 * node + 1, middle + 1, right, query_left, query_right);

                tree_node left_node = query(node * 2, left, middle, query_left, query_right), 
                right_node = query(node * 2 + 1, middle + 1, right, query_left, query_right);

                return update_node(left_node, right_node);
        }
}

int main(){
        cin>>n>>q;
        for(int i = 1; i <= n; i++)cin>>a[i];

        build(1, 1, n);

        while(q--){
                int left, right;
                cin>>left>>right;
                cout<<query(1, 1, n, left, right).scmax<<ln;
        }

        return 0;
}