#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 200000
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int n,m,rt[N+1],h[N+1],p[N+1],pst[N+1];
long long ans;
struct seg
{
    struct node
    {
	int ls,rs,data;
	long long data2;
    };
    node tree[20*N+1];
    int length;
    void push_up(int k)
    {
	tree[k].data=tree[tree[k].ls].data+tree[tree[k].rs].data,tree[k].data2=tree[tree[k].ls].data2+tree[tree[k].rs].data2;
	return;
    }
    int add(int k,int L,int R,int x,int d)
    {
	int nw=++length;
	tree[nw]=tree[k];
	if (L==R)
	{
	    tree[nw].data+=d,tree[nw].data2+=d*h[p[x]];
	    return nw;
	}
	int mid=(L+R)>>1;
	if (x<=mid) tree[nw].ls=add(tree[nw].ls,L,mid,x,d);
	else tree[nw].rs=add(tree[nw].rs,mid+1,R,x,d);
	push_up(nw);
	return nw;
    }
    int find(int p,int q,int L,int R,int x)
    {
	if (L==R) return L;
	int mid=(L+R)>>1;
	if (x<=tree[tree[q].ls].data-tree[tree[p].ls].data) return find(tree[p].ls,tree[q].ls,L,mid,x);
	else return find(tree[p].rs,tree[q].rs,mid+1,R,x-(tree[tree[q].ls].data-tree[tree[p].ls].data));
    }
    long long query(int k,int L,int R,int l,int r)
    {
	if (l>r) return 0;
	if (L==l&&R==r) return tree[k].data2;
	int mid=(L+R)>>1;
	if (r<=mid) return query(tree[k].ls,L,mid,l,r);
	else if (l>=mid+1) return query(tree[k].rs,mid+1,R,l,r);
	else return query(tree[k].ls,L,mid,l,mid)+query(tree[k].rs,mid+1,R,mid+1,r);
    }
};
seg T;
bool cmp(int x,int y)
{
    return h[x]<h[y];
}
int main()
{
    int l,r,ps,ps2,ps3;
    n=read(),m=read();
    for (int i=1;i<=n;++i) h[i]=read(),p[i]=i;
    sort(p+1,p+n+1,cmp);
    for (int i=1;i<=n;++i) pst[p[i]]=i;
    for (int i=1;i<=n;++i) rt[i]=T.add(rt[i-1],1,n,pst[i],1);
    while (m--)
    {
	l=read(),r=read(),ans=0;
	if (!((r-l+1)&1))
	{
	    ps=T.find(rt[l-1],rt[r],1,n,(r-l+1)>>1),ps2=T.find(rt[l-1],rt[r],1,n,((r-l+1)>>1)+1);
	    ans-=((T.query(rt[r],1,n,1,ps-1)-T.query(rt[l-1],1,n,1,ps-1))<<1);
	    ans+=((T.query(rt[r],1,n,ps2+1,n)-T.query(rt[l-1],1,n,ps2+1,n))<<1);
	    printf("%lld\n",ans+h[p[ps2]]-h[p[ps]]);
	}
	else
	{
	    ps=T.find(rt[l-1],rt[r],1,n,((r-l+1)>>1)),ps2=T.find(rt[l-1],rt[r],1,n,((r-l+1)>>1)+1),ps3=T.find(rt[l-1],rt[r],1,n,((r-l+1)>>1)+2);
	    ans-=((T.query(rt[r],1,n,1,ps-1)-T.query(rt[l-1],1,n,1,ps-1))<<1);
	    ans+=((T.query(rt[r],1,n,ps3+1,n)-T.query(rt[l-1],1,n,ps3+1,n))<<1);
	    printf("%lld\n",ans+h[p[ps3]]-h[p[ps]]+max(h[p[ps2]]-h[p[ps]],h[p[ps3]]-h[p[ps2]]));
	}
    }
    return 0;
}