#include <bits/stdc++.h>
using namespace std;

/// INPUT / OUTPUT
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

/// STRUCTURES
struct tree_node
{
    int scmax;
    int prefix_sum;
    int suffix_sum;
    int sum;
};

/// GLOBAL VARIABLES
const int NMAX = 1e5+5;
int n, q, ans;
int arr[NMAX];
vector<pair<int,int>>queries;
tree_node tree[4*NMAX];

inline tree_node update_node(tree_node left, tree_node right)
{
    tree_node curr_node;
    curr_node.sum = left.sum + right.sum;
    curr_node.prefix_sum = max(left.sum + right.prefix_sum, left.prefix_sum);
    curr_node.suffix_sum = max(right.sum + left.suffix_sum, right.suffix_sum);
    curr_node.scmax = max(left.suffix_sum + right.prefix_sum, max(left.suffix_sum, right.prefix_sum));
    return curr_node;
}

inline void build(int node, int st, int dr)
{
    if(st == dr)
    {
        tree[node].scmax = arr[st];
        tree[node].prefix_sum = arr[st];
        tree[node].suffix_sum = arr[st];
        tree[node].sum = arr[st];
    }
    else
    {
        int mid = (st + dr) / 2;
        build(node * 2, st, mid);
        build(node * 2 + 1, mid + 1, dr);
        tree[node] = update_node(tree[node*2], tree[node*2+1]);
    }
}

inline tree_node query(int node, int st, int dr, int arbst, int arbdr)
{
    if(arbdr >= dr && arbst <= st)
    {
        return tree[node];
    }
    else
    {
        int mid = (st + dr) / 2;
        if(arbdr <= mid)
            return query(node*2, st, mid, arbst, arbdr);
        if(mid + 1 <= arbst)
            return query(node*2+1, mid + 1, dr, arbst, arbdr);
        tree_node left_node = query(node*2, st, mid, arbst, arbdr);
        tree_node right_node = query(node*2+1, mid + 1, dr, arbst, arbdr);
        return update_node(left_node, right_node);
    }
}

/// READING THE INPUT
int main()
{
    fin >> n >> q;
    for(int i = 1; i <= n; ++ i)
    {
        fin >> arr[i];
    }
    build(1,1,n);
    for(int i = 1; i <= q; ++ i)
    {
        int x, y;
        fin >> x >> y;
        fout << query(1, 1, n, x, y).scmax << '\n';
    }
}