#include<bits/stdc++.h>
#define ll long long
using namespace std;
template <class T> inline T read(){
	T r=0,f=0;char c=getchar();
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) r=(r<<3)+(r<<1)+(c^48),c=getchar();
	return f?-r:r;
}
const int N=5e5+5;
int n,m,block,a[N],b[N];
struct query{
	int l,r,id;
	bool operator <(const query &x)const{
		return l/block==x.l/block?(l/block)&1?r<x.r:r>x.r:l<x.l;
	}
}Q[N];
int L=1,R=0;
ll sum,ans[N];
bitset<N> S1,S2;
inline int findpre(int x){int t=S1._Find_next(x); return t^N?b[t]:N;}
inline int findnxt(int x){int t=S2._Find_next(500000-x); return t^N?b[500000-t]:N;}
inline void insert(int x){S1.set(x),S2.set(500000-x);}
inline void erase(int x){S1.set(x,0),S2.set(500000-x,0);}
inline int abs(int x){return x<0?-x:x;}
inline void add(int x){
	int u=findpre(a[x]),v=findnxt(a[x]);
	if(u!=N&&v!=N) sum-=abs(u-v);
	if(u!=N) sum+=abs(u-x);
	if(v!=N) sum+=abs(v-x);
	insert(a[x]);
}
inline void del(int x){
	int u=findpre(a[x]),v=findnxt(a[x]);
	if(u!=N&&v!=N) sum+=abs(u-v);
	if(u!=N) sum-=abs(u-x);
	if(v!=N) sum-=abs(v-x);
	erase(a[x]);
}
signed main(){
	n=read<int>(),m=read<int>(),block=n/sqrt(m);
	for(int i=1;i<=n;++i) a[i]=read<int>(),b[a[i]]=i;
	for(int i=1;i<=m;++i) Q[i].l=read<int>(),Q[i].r=read<int>(),Q[i].id=i;
	sort(Q+1,Q+1+m);
	for(int i=1;i<=m;++i){
		while(R<Q[i].r) add(++R);
		while(L<Q[i].l)	del(L++);
		while(L>Q[i].l) add(--L);
		while(R>Q[i].r)	del(R--);
		ans[Q[i].id]=sum;
	}
	for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
	return 0;
}

answer.code:1:9: fatal error: bits/stdc++.h: No such file or directory
 #include<bits/stdc++.h>
         ^~~~~~~~~~~~~~~
compilation terminated.