rt , TLE on # 10

#include<bits/stdc++.h>
#define int long long
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
inline int qr() {
	char c;bool f(1);
	while(!isdigit(c=getchar()))f=c!='-';
	int x(c^48);
	while(isdigit(c=getchar()))x=x*10+(c^48);
	return f?x:-x;
}
const int N(3e5+5);
int n,m,a[N+5],b[N+5],c[N+5],d[N+5];
map<int,int>cnt;
namespace Disc{
	int disc[N+5],tot;
	void insert(int x) {
		disc[++tot]=x;
	}
	void init() {
		sort(disc+1,disc+1+tot);
		tot=unique(disc+1,disc+1+tot)-(disc+1);
	}
	int ask(int x) {
		return lower_bound(disc+1,disc+1+tot,x)-disc;
	}
}; // namespace Disc
using namespace Disc;

namespace MD {
	#define QWQ array<int,3>
	QWQ inq[N+5];
	int block;
	bool cmp(QWQ a,QWQ b) {
		int t1(a[0]/block),t2(b[0]/block);
		if(t1==t2) return t1&1?(a[1]<b[1]):(a[1]>b[1]);
		return t1<t2;
	}
	
	int _ans[N+5],l(1),r,ans,cnt1[N+5],cnt2[N+5];
	
	void add(int p) {
		ans+=cnt2[b[p]]+cnt1[c[p]]+cnt1[d[p]];
		++cnt1[b[p]],++cnt2[c[p]],++cnt2[d[p]];
	}
	
	void del(int p) {
		--cnt1[b[p]],--cnt2[c[p]],--cnt2[d[p]];
		ans-=cnt2[b[p]]+cnt1[c[p]]+cnt1[d[p]];
	}
	
	void work() {
		block=sqrt(n);
		sort(inq+1,inq+1+m,cmp);
		U(i,1,m) {
			QWQ now(inq[i]);
			while(l>now[0]) add(--l);
			while(r<now[1]) add(++r);
			while(l<now[0]) del(l++);
			while(r>now[1]) del(r--);
			_ans[now[2]]=ans;
		}
	}
}; // namespace MD
using namespace MD;
signed main() {
	n=qr(),m=qr();
	U(i,1,n) a[i]=qr(),insert(a[i]),++cnt[a[i]];
	init();
	U(i,1,n) b[i]=ask(a[i]);
	U(i,1,n) {
		if(b[i]==1) c[i]=2;
		else if(b[i]==tot) c[i]=tot-1;
		else if(cnt[a[i]]!=1) c[i]=b[i];
		else {
			int tmp1(disc[b[i]]-disc[b[i]-1]);
			int tmp2(disc[b[i]+1]-disc[b[i]]);
			if(tmp1<=tmp2) c[i]=b[i]-1;
			if(tmp2<=tmp1) d[i]=b[i]+1;
		}
	}
	U(i,1,m) inq[i]={qr(),qr(),i};
	work();
	int Ans(0);
	U(i,1,m) /*cout<<_ans[i]<<endl,*/Ans+=i*_ans[i];
	printf("%lld",Ans);
}