#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 1000000000
using namespace std;
int n,m;
int a[200005];
int l,r;
struct node{
	int l,r,c;
	ll s;
}tree[10000005];
int root[200005],cnt;
void ins(int &now,int nowl,int nowr,int pos){
	int pre=now;
	now=++cnt;
	tree[now]=tree[pre];
	tree[now].c++,tree[now].s+=pos;
	if (nowl==nowr)return;
	int mid=(nowl+nowr)/2;
	if (pos<=mid)ins(tree[now].l,nowl,mid,pos);
	else ins(tree[now].r,mid+1,nowr,pos);
	return;
}
ll ask(int a,int b,int nowl,int nowr,int k){
	if (nowl==nowr)return 1ll*k*nowl;
	int mid=(nowl+nowr)/2;
	int c=tree[tree[a].l].c-tree[tree[b].l].c;
	if (c>=k)return ask(tree[a].l,tree[b].l,nowl,mid,k);
	return tree[tree[a].l].s-tree[tree[b].l].s+ask(tree[a].r,tree[b].r,mid+1,nowr,k-c);
}
int find(int a,int b,int nowl,int nowr,int k){
	if (nowl==nowr)return nowl;
	int mid=(nowl+nowr)/2;
	int c=tree[tree[a].l].c-tree[tree[b].l].c;
	if (c>=k)return find(tree[a].l,tree[b].l,nowl,mid,k);
	return find(tree[a].r,tree[b].r,mid+1,nowr,k-c);
}
ll work(int l,int r){
	ll ans=0;
	int len=(r-l+1);
	if (len&1){
		int mid=(len+1)/2;
		ans=2*ask(root[r],root[l-1],1,maxn,len)-4*ask(root[r],root[l-1],1,maxn,mid-1);
		int a=find(root[r],root[l-1],1,maxn,mid-1);
		int b=find(root[r],root[l-1],1,maxn,mid);
		int c=find(root[r],root[l-1],1,maxn,mid+1);
		ans-=min(0ll+b+c,3ll*b-a);
	}
	else{
		int mid=len/2;
		ans=2*ask(root[r],root[l-1],1,maxn,len)-4*ask(root[r],root[l-1],1,maxn,mid);
		ans-=find(root[r],root[l-1],1,maxn,mid+1);
		ans+=find(root[r],root[l-1],1,maxn,mid);
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	for (int i=1;i<=n;i++){
		root[i]=root[i-1];
		ins(root[i],1,maxn,a[i]);
	}
	while(m--){
		scanf("%d%d",&l,&r);
		printf("%lld\n",work(l,r));
	}
	return 0;
}