# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int rt[200010],h[200010],hh[200010],lc[4000010],rc[4000010],cnt[4000010],tot;
ll sum[4000010];
void update(int &rt,int l,int r,int x)
{
	cnt[++tot]=cnt[rt];sum[tot]=sum[rt];lc[tot]=lc[rt];rc[tot]=rc[rt];rt=tot;
	if(l==r) return cnt[rt]++,sum[rt]+=hh[l],void();
	int mid=(l+r)/2;
	if(x<=mid) update(lc[rt],l,mid,x);
	else update(rc[rt],mid+1,r,x);
	cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
	sum[rt]=sum[lc[rt]]+sum[rc[rt]];
}
ll query1(int r1,int r2,int l,int r,int x)
{
	if(l==r) return x*hh[l];
	int mid=(l+r)/2;
	if(2*(cnt[lc[r2]]-cnt[lc[r1]])>=x) return query1(lc[r1],lc[r2],l,mid,x);
	else return 2*(sum[lc[r2]]-sum[lc[r1]])+query1(rc[r1],rc[r2],mid+1,r,x-2*(cnt[lc[r2]]-cnt[lc[r1]]));
}
ll query2(int r1,int r2,int l,int r,int x)
{
	if(l==r) return x*hh[l];
	int mid=(l+r)/2;
	if(2*(cnt[rc[r2]]-cnt[rc[r1]])>=x) return query2(rc[r1],rc[r2],mid+1,r,x);
	else return 2*(sum[rc[r2]]-sum[rc[r1]])+query2(lc[r1],lc[r2],l,mid,x-2*(cnt[rc[r2]]-cnt[rc[r1]]));
}
int query(int r1,int r2,int l,int r,int x)
{
	if(l==r) return hh[l];
	int mid=(l+r)/2;
	if(cnt[lc[r2]]-cnt[lc[r1]]>=x) return query(lc[r1],lc[r2],l,mid,x);
	else return query(rc[r1],rc[r2],mid+1,r,x-(cnt[lc[r2]]-cnt[lc[r1]]));
}
int main()
{
	int n,m,l,r;
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&h[i]),hh[i]=h[i];
	sort(hh+1,hh+n+1);
	int len=unique(hh+1,hh+n+1)-hh-1;
	for(int i=1;i<=n;i++) h[i]=lower_bound(hh+1,hh+len+1,h[i])-hh;
	for(int i=1;i<=n;i++) update(rt[i]=rt[i-1],1,len,h[i]);
	while(m--)
	{
		scanf("%d%d",&l,&r);
		ll ans=query2(rt[l-1],rt[r],1,len,r-l)-query1(rt[l-1],rt[r],1,len,r-l);
		if((r-l+1)&1)
		{
			auto kth=[&](int k){return query(rt[l-1],rt[r],1,len,k);};
			ll x1=kth((r-l)/2),x2=kth((r-l)/2+1),x3=kth((r-l)/2+2);
			ans-=min(x2-x1,x3-x2);
		}
		printf("%lld\n",ans);
	}
	return 0;
}