#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef signed long long ll;
typedef unsigned int uint;
const int nmax = 100000;

struct node {
    int max_left;
    int max_right;
    int sum_total;
    int max_sum;

    node() {
        max_left = max_right = sum_total = max_sum = -9999999;
    }
};
node arbint[nmax * 4 + 66];
int v[nmax];

uint n, m;

node merge_nodes(node &left, node &right) {
    node parent;

    parent.sum_total = left.sum_total + right.sum_total;

    parent.max_left = max(
        left.max_left,
        left.sum_total + right.max_left
    );

    parent.max_right = max(
        right.max_right,
        right.sum_total + left.max_right
    );

    parent.max_sum = max({
        left.max_sum,
        right.max_sum,
        left.max_right + right.max_left
    });

    return parent;
}

void build(uint _node, uint _left, uint _right) {
    if (_left == _right) {
        arbint[_node].max_left = arbint[_node].max_right = arbint[_node].sum_total = arbint[_node].max_sum = v[_left];
        return ;
    }

    uint mid = (_left + _right) / 2;
    uint left_node = 2 * _node + 1;
    uint right_node = 2 * _node + 2;


    build(left_node, _left, mid);
    build(right_node, mid + 1, _right);

    arbint[_node] = merge_nodes(arbint[left_node], arbint[right_node]);
}

node result;
uint seg_left, seg_right;
void prep_query(uint a, uint b) {
    //result.max_left = result.max_right = result.max_sum = result.sum_total = INT_MIN;
    seg_left = a;
    seg_right = b;
}

node query_helper(uint _node, uint _left, uint _right) {
    //printf("%u %u %u\n", _node, _left, _right);
    if (_left >= seg_left && _right <= seg_right) {
        return arbint[_node];
    }

    if (_left > seg_right || _right < seg_left) {
        node null_node;
        return null_node;
    }

    uint mid = (_left + _right) / 2;
    node left = query_helper(2 * _node + 1, _left, mid);
    node right = query_helper(2 * _node + 2, mid + 1, _right);

    //result = merge_nodes(left, right);
    //printf("%d\n", result.max_sum);
    return merge_nodes(left, right);
}

void query(uint _left, uint _right) {
    prep_query(_left, _right);
    result = query_helper(0, 0, n - 1);
    printf("%d\n", result.max_sum);
}

void show() {
    for (int i=0;i<n*4;i++){
        cout << arbint[i].sum_total<<" ";
    }cout<<endl<<endl;
    for (int i=0;i<n*4;i++){
        cout << arbint[i].max_sum<<" ";
    }cout<<endl;
}

int main() {
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);

    //memset(arbint, INT_MIN, sizeof(node) * (nmax * 4 + 66));
    scanf("%u%u", &n, &m);
    for (uint i=0; i<n;i++) {
        scanf("%d", &v[i]);
    }

    build(0, 0, n - 1);
    //show();
    //cout << arbint[0].max_sum << "\n";

    uint x, y;
    for (uint i=0;i<m;i++){
        scanf("%u %u", &x, &y);
        query(x - 1, y - 1);
    }

    return 0;
}