#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int BB = 500;
struct Seg {
	int L;
	int R;
	int idx;
	bool operator<(const Seg &right)const {
		if (L / BB == right.L / BB) {
			return R < right.R;
		}
		else {
			return L < right.L;
		}
	}
};

vector<int> A;
vector<pair<int, int> > B;
set<int> st;
int center;
int sum;
int k;
int rem(int i) {
	if (center > i) {
		k--;
	}
	if (center >= i) {
		sum += A[B[i].second];
	}
	else {
		sum -= A[B[i].second];

	}
	st.erase(i);
}

int add(int i) {
	if (center > i) {
		k++;
		sum -= A[B[i].second];
	}
	else {
		sum += A[B[i].second];
	}
	st.insert(i);
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, Q;
	cin >> N >> Q;
	A.resize(N);
	B.resize(N);
	vector<int> res(Q);
	vector<int> C(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B[i].first = A[i];
		B[i].second = i;
	}
	sort(B.begin(), B.end());
	for (int i = 0; i < N; i++) {
		C[B[i].second] = i;
	}
	vector<Seg> seg(Q);
	for (int i = 0; i < Q; i++) {
		cin >> seg[i].L >> seg[i].R;
		seg[i].L--;
		seg[i].R--;
		seg[i].idx = i;
	}
	sort(seg.begin(), seg.end());
	int L = 0;
	int R = 0;
	st.insert(C[0]);
	center = C[0];
	sum = -A[0];
	auto s = st.begin();
	for (int i = 0; i < Q; i++) {

		while (L > seg[i].L) {
			L--;
			add(C[L]);
		}
		while (R < seg[i].R) {
			R++;
			add(C[R]);
		}
		while (L < seg[i].L) {
			rem(C[L]);
			L++;
		}
		while (R > seg[i].R) {
			rem(C[R]);
			R--;
		}
		auto s = st.lower_bound(center);
		if (s == st.end()) {
			--s;
			--k;
		}
		else {
			if ((*s) != center) {
				sum -= 2 * A[B[*s].second];
			}
		}
		while (k > (st.size() - 1) / 2) {
			sum += 2 * A[B[*s].second];
			--s;
			--k;
		}

		while (k < (st.size() - 1) / 2) {
			++s;
			++k;
			sum -= 2 * A[B[*s].second];
		}


		center = (*s);
		//cerr << A[*s] << endl;

		res[seg[i].idx] = A[B[center].second] * (st.size() % 2) + sum;

	}

	for (int i = 0; i < Q; i++) {
		cout << res[i] << endl;
	}
}