#include <fstream>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int N_MAX = 1e5;
const int V_MIN = -1e5;
const int SEGMENT_TREE_DIM = 2 * N_MAX;

template<typename T>
class SegmentTree{
private:
		T segmentTree[SEGMENT_TREE_DIM];

public:

		void build(int node, int left, int right, ifstream& fin){
			if(left == right){
				T x;
				fin >> x;
				segmentTree[node] = x;
			}else{
				int middle = (left + right) / 2;
				int leftChild = node + 1;
				int rightChild = node + 2 * (middle - left + 1);
				build(leftChild, left, middle, fin);
				build(rightChild, middle + 1, right, fin);
				segmentTree[node] = segmentTree[leftChild] + segmentTree[rightChild];
			}
		}

		void update(int node, int left, int right, int pos, T val){
			if(left == right)
				segmentTree[node] = val;
			else{
				int middle = (left + right) / 2;
				int leftChild = node + 1;
				int rightChild = node + 2 * (middle - left + 1);
				if(pos <= middle)
					update(leftChild, left, middle, pos, val);
				else
					update(rightChild, middle + 1, right, pos, val);
				segmentTree[node] = segmentTree[leftChild] + segmentTree[rightChild];
			}
		}

		T query(int node, int left, int right, int qleft, int qright){
			T retval{};

			if(left >= qleft && right <= qright)
				retval = segmentTree[node];
			else{
				T aux{};
				int middle = (left + right) / 2;
				int leftChild = node + 1;
				int rightChild = node + 2 * (middle - left + 1);
				if(qleft <= middle)
					retval = query(leftChild, left, middle, qleft, qright);
				if(middle + 1 <= qright)
					aux = query(rightChild, middle + 1, right, qleft, qright);

				if(aux.has_changed()){
					if(retval.has_changed())
						retval += aux;
					else
						retval = aux;
				}
			}

			return retval;
		}
};

struct Sequance{
		long long prefixSum, suffixSum, biggestSum, sum;

		Sequance(){
			prefixSum = suffixSum = biggestSum = sum = (long long) N_MAX * V_MIN - 1;
		}

		Sequance operator+(const Sequance& other) const{
			Sequance res{};

			res.prefixSum = max(prefixSum, sum + other.prefixSum);

			res.suffixSum = max(other.suffixSum, other.sum + suffixSum);

			res.sum = sum + other.sum;

			res.biggestSum = max(max(biggestSum, other.biggestSum), suffixSum + other.prefixSum);

			return res;
		}

		friend void operator+=(Sequance& a, const Sequance& b){
			a = a + b;
		}

		friend ifstream& operator>>(ifstream& fin, Sequance& s){
			fin >> s.sum;
			s.prefixSum = s.suffixSum = s.biggestSum = s.sum;

			return fin;
		}

		bool operator!=(const Sequance& other) const{
			return prefixSum != other.prefixSum || suffixSum != other.suffixSum || sum != other.sum ||
			       biggestSum != other.biggestSum;
		}

		bool has_changed(){
			Sequance aux{};
			return *this != aux;
		}
};

SegmentTree<Sequance> segtree;

int main(){
	int n, queries;
	fin >> n >> queries;

	segtree.build(0, 0, n - 1, fin);

	for(int i = 0; i < queries; ++i){
		int a, b;
		fin >> a >> b;

		fout << segtree.query(0, 0, n - 1, a - 1, b - 1).biggestSum << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}