rt

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int n,m,a[N],b[N],bl[N],c[N],len;
int t[N];
ll p[N][2];
inline void add(int k,int x){for(;k<=n;k+=k&(-k))t[k]+=x;}
inline int ask(int k){
	int ans=0;
	for(;k>0;k-=k&(-k))ans+=t[k];
	return ans;
}
struct query{int l,r,id;ll ans;}q[N];
bool cmp(query a,query b){
	if(bl[a.l]==bl[b.l]){
		if(bl[a.l]&1)return a.r<b.r;
		else return a.r>b.r;
	}
	return bl[a.l]<bl[b.l];
}
bool cmp1(query a,query b){return a.id<b.id;}
struct P{int l,r,id,op,k;}; 
vector<P> v[N][2];
void init(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],c[i]=a[i];
	sort(c+1,c+n+1);
	int s=n/(sqrt(n)+1);
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(c+1,c+n+1,a[i])-c,bl[i]=(i-1)/s+1;
		add(a[i],1);
		p[i][0]=i-ask(a[i]);
	}
	memset(t,0,sizeof(t));
	for(int i=n;i>=1;i--){
		add(a[i],1);
		p[i][1]=ask(a[i]-1);
	}
	for(int i=1;i<=n;i++)p[i][0]+=p[i-1][0],p[i][1]+=p[i-1][1];
}
void work(){
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		q[i]=(query){l,r,i};
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=1,r=0;i<=m;i++){
		int L=q[i].l,R=q[i].r;
		if(r<R)v[l-1][1].push_back((P){r+1,R,i,-1}),q[i].ans+=(ll)p[R][0]-p[r][0],r=R;
		if(r>R)v[l-1][1].push_back((P){R+1,r,i,1}),q[i].ans-=(ll)p[r][0]-p[R][0],r=R;
		if(l>L)v[r+1][0].push_back((P){L,l-1,i,-1}),q[i].ans+=(ll)p[l-1][1]-p[L-1][1],l=L;
		if(l<L)v[r+1][0].push_back((P){l,L-1,i,1}),q[i].ans-=(ll)p[L-1][1]-p[l-1][1],l=L;
	}
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i++){
		add(a[i],1);
		for(P s:v[i][1])for(int t=s.l;t<=s.r;t++)q[s.id].ans+=(ll)s.op*(i-ask(a[t]));
	}
	memset(t,0,sizeof(t));
	for(int i=n;i>=1;i--){
		add(a[i],1);
		for(P s:v[i][0])for(int t=s.l;t<=s.r;t++)q[s.id].ans+=(ll)s.op*ask(a[t]-1);
	}
	for(int i=1;i<=m;i++)q[i].ans+=q[i-1].ans;
	sort(q+1,q+m+1,cmp1);
}
void print(){for(int i=1;i<=m;i++)cout<<q[i].ans<<endl;}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	init();
	work();
	print();
}