#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N],b[N],c[N],ans[N],n,m,B,sum;
void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
int getsum(int x){int res=0;for(;x;x-=x&-x)res+=c[x];return res;}
struct node{int l,r,id;}q[N];
bool cmp(node n1,node n2){return (n1.l/B)!=(n2.l/B)?n1.l<n2.l:n1.r<n2.r;}
signed main()
{
	cin>>n>>m;B=sqrt(n);
	for(int i=1;i<=n;i++)cin>>b[i],a[i]=b[i];
	sort(b+1,b+n+1);int k=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+k+1,a[i])-b;
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;q[i].l++;
		if(q[i].l>q[i].r)swap(q[i].l,q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		while(l>q[i].l)add(a[--l],1),sum+=getsum(a[l]-1);
		while(r<q[i].r)add(a[++r],1),sum+=r-l+1-getsum(a[r]);
		while(l<q[i].l)add(a[l++],-1),sum-=getsum(a[l-1]-1);
		while(r>q[i].r)add(a[r--],-1),sum-=r-l+1-getsum(a[r+1]);
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}