// "I am the true mogger."
// 					-MihneaTheMogger
// 
// prob Range Updates and Sums
// 
// tl 1000
// ml 512
// 
// LOT

#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false);\
                               cin.tie(nullptr);\
                 			  cout.tie(nullptr);
using namespace std;

#define int int64_t 
#define YES cout<<"YES"    
#define YESn cout<<"YES\n" 
#define NO cout<<"NO"     
#define NOn cout<<"NO\n"       

#define MORE_TESTS 0    
#define FASTIO 1     
int32_t TESTCASE_COUNT = 1, TESTCASE;

struct SegmentTreeNode {
    int total;
    int max_prefix;
    int max_suffix;
    int max_sum;

    SegmentTreeNode() : total(INT32_MIN), max_prefix(INT32_MIN), max_suffix(INT32_MIN), max_sum(INT32_MIN) {}
};

class SegmentTree {
private:
    vector<SegmentTreeNode> tree;
    vector<int> array;
    int size;

    SegmentTreeNode combine(SegmentTreeNode left, SegmentTreeNode right) {
        SegmentTreeNode result;
        result.total = left.total + right.total;
        result.max_prefix = max(left.max_prefix, left.total + right.max_prefix);
        result.max_suffix = max(right.max_suffix, right.total + left.max_suffix);
        result.max_sum = max({left.max_sum, right.max_sum, left.max_suffix + right.max_prefix});
        return result;
    }

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node].total = array[start];
            tree[node].max_prefix = max((int)-1e5, array[start]);
            tree[node].max_suffix = max((int)-1e5, array[start]);
            tree[node].max_sum = max((int)-1e5, array[start]);
        } else {
            int mid = (start + end) / 2;
            build(2 * node + 1, start, mid);
            build(2 * node + 2, mid + 1, end);
            tree[node] = combine(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    SegmentTreeNode query(int node, int start, int end, int L, int R) {
        if (R < start || end < L) {
            return SegmentTreeNode(); // return a node with 0 values
        }
        if (L <= start && end <= R) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        SegmentTreeNode left = query(2 * node + 1, start, mid, L, R);
        SegmentTreeNode right = query(2 * node + 2, mid + 1, end, L, R);
        return combine(left, right);
    }

public:
    SegmentTree(const vector<int>& arr) : array(arr) {
        size = arr.size();
        tree.resize(4 * size);
        build(0, 0, size - 1);
    }

    int query(int L, int R) {
        return query(0, 0, size - 1, L, R).max_sum;
    }
};

void Solve ()
{
#ifndef LOCAL
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdtout);
#endif
	int n, m; cin >> n >> m;
	vector<int> v(n);
	for (int i = 0; i < n; i ++) {
		cin >> v[i];
	}
	SegmentTree aint(v);
	while (m --) {
		int l, r; cin >> l >> r;
		l --, r --;
		cout << aint.query(l, r) << '\n';
	}
}

/*

*/

int32_t main ()
{
    #if FASTIO == 1
    FastIO;
    #endif
    #if MORE_TESTS == 1
    cin >> TESTCASE_COUNT;
    #endif
    for (TESTCASE = 1; TESTCASE <= TESTCASE_COUNT; TESTCASE ++)
        Solve ();
}

/*
___  ___          _        ______         ___  ____ _                    _____ _         ___  ___
|  \/  |         | |       | ___ \        |  \/  (_) |                  |_   _| |        |  \/  |
| .  . | __ _  __| | ___   | |_/ /_   _   | .  . |_| |__  _ __   ___  __ _| | | |__   ___| .  . | ___   __ _  __ _  ___ _ __
| |\/| |/ _` |/ _` |/ _ \  | ___ \ | | |  | |\/| | | '_ \| '_ \ / _ \/ _` | | | '_ \ / _ \ |\/| |/ _ \ / _` |/ _` |/ _ \ '__|
| |  | | (_| | (_| |  __/  | |_/ / |_| |  | |  | | | | | | | | |  __/ (_| | | | | | |  __/ |  | | (_) | (_| | (_| |  __/ |
\_|  |_/\__,_|\__,_|\___|  \____/ \__, |  \_|  |_/_|_| |_|_| |_|\___|\__,_\_/ |_| |_|\___\_|  |_/\___/ \__, |\__, |\___|_|
                                   __/ |                                                                __/ | __/ |
                                  |___/                                                                |___/ |___/
*/