#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
#define N 200005
using namespace std;
int tr[N*32],lson[N*32],rson[N*32],sm[N*32];
int cnt;
int a[N],b[N],p[N],n,q,rt[N];
void update(int &k,int lst,int l,int r,int L,int x)
{
	k=++cnt;
	sm[k]=sm[lst];
	tr[k]=tr[lst];
	lson[k]=lson[lst];
	rson[k]=rson[lst];
	tr[k]++;
	sm[k]+=x;
	if (l==r) return;
	int mid=l+(r-l)/2;
	if (L<=mid) update(lson[k],lson[lst],l,mid,L,x);
	else update(rson[k],rson[lst],mid+1,r,L,x);
}
int qry(int k,int lst,int l,int r,int x)
{
	if (x==0) return 0;
	if (l==r)
	{
		return sm[k]-sm[lst];
	}
	int mid=l+(r-l)/2;
	if (tr[rson[k]]-tr[rson[lst]]<x)
	{
		x-=tr[rson[k]]-tr[rson[lst]];
		return qry(lson[k],lson[lst],l,mid,x)+sm[rson[k]]-sm[rson[lst]];
	}
	return qry(rson[k],rson[lst],mid+1,r,x);
}		
void BellaKira()
{
	cin>>n>>q;
	for (int i=1;i<=n;i++)
		cin>>a[i],p[i]=i;
	sort(p+1,p+n+1,[&](int x,int y)
	{
		return a[x]<a[y];
	});
	for (int i=1;i<=n;i++) b[p[i]]=i;
	for (int i=1;i<=n;i++)
	{
		update(rt[i],rt[i-1],1,n,b[i],a[i]);
	}
	while (q--)
	{
		int l,r;
		cin>>l>>r;
		if ((r-l+1)&1)
		{
			int tot=(r-l+1)/2;
			int ans=qry(rt[r],rt[l-1],1,n,tot)*4-
			1*qry(rt[r],rt[l-1],1,n,tot+tot-1)
			-qry(rt[r],rt[l-1],1,n,tot+tot+1);
			cout<<ans<<'\n';
		} else
		{
			int tot=(r-l+1)/2;
			int ans=qry(rt[r],rt[l-1],1,n,tot)*4-
			2*qry(rt[r],rt[l-1],1,n,tot+tot)
			-(qry(rt[r],rt[l-1],1,n,tot)-qry(rt[r],rt[l-1],1,n,tot-1))
			+(qry(rt[r],rt[l-1],1,n,tot+tot)-qry(rt[r],rt[l-1],1,n,tot+tot-1));
			cout<<ans<<'\n';
		}
	}
			
			
	
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}