#include <bits/stdc++.h>
#define ll long long
using namespace std;
//#define fread fread_unlocked
//#define fwrite fwrite_unlocked
const int LEN=10000005;int ED1=-1;
char Buf[LEN],*OP=Buf,*ED=Buf,Buf1[LEN+2];
inline void flush(){fwrite(Buf1,1,ED1+1,stdout),ED1=-1;}
inline char gc(){return (OP==ED)?(ED=(OP=Buf)+fread(Buf,1,LEN,stdin),*OP++):(*OP++);}
inline void pc(char ch){Buf1[ED1==LEN?(flush(),ED1=0):++ED1]=ch;}
inline int read(){
	int x=0;char ch=gc();
	while(!isdigit(ch)) ch=gc();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return x;
}
inline void write(unsigned long long x){
	if(x==0){pc('0');pc('\n');return;}
	char ch[20];short cnt=-1;
	while(x){
		ch[++cnt]=(char)((x%10)^48);
		x/=10;
	}
	for(int i=cnt;i>=0;--i) pc(ch[i]);
	pc('\n');
}
const int B=800;
const int B2=1024;
const int bB=10;
struct NTT{
	unsigned int a[500005],s[500005];
	NTT(){memset(a,0,sizeof(a));memset(s,0,sizeof(s));}
	void add(int x){
		++a[x];
		++s[((x-1)>>bB)+1];
	}
	unsigned long long ask(int l,int r){
		int bl=((l-1)>>bB)+1,br=((r-1)>>bB)+1;
		ll res=0;
		if(bl==br){
			for(int i=l;i<=r;++i) res+=a[i];
		}else{
			for(int i=l;i<=(bl<<bB);++i) res+=a[i];
			for(int i=bl+1;i<=br;++i) res+=s[i];
		}
		return res;
	}
};
struct Query{
	int l,r,id;
	Query(){}
	Query(int a,int b,int c){l=a;r=b;id=c;}
};
unsigned long long F[500005];
struct List{
	int a[500005];
	int s[500005];
	bool b[500005];
	int to[500005];
	int top;
	int stk[500005];
	unsigned long long ans[2500005];
	void clear(int n){for(int i=0;i<=n+1;++i)b[i]=to[i]=a[i]=s[i]=0;top=0;}
	void geta(int* aa,int n){for(int i=1;i<=n;++i)a[i]=aa[i],s[i]=s[i-1]+a[i];}
	void insert(int x){
//		cerr<<"insert "<<x<<endl;
		++top;
		ans[top]=ans[top-1];
		stk[top]=x;
		b[x]=1;
		if(!b[x-1]&&!b[x+1]){
			to[x]=x;
			return;
		}
		if(!b[x-1]){
			ans[top]-=F[s[to[x+1]]-s[x]];
			to[to[x]=to[x+1]]=x;
			ans[top]+=F[s[to[x]]-s[x-1]];
		}else if(!b[x+1]){
			ans[top]-=F[s[x-1]-s[to[x-1]-1]];
			to[to[x]=to[x-1]]=x;
			ans[top]+=F[s[x]-s[to[x]-1]];
		}else{
			ans[top]+=(s[x-1]-s[to[x-1]-1])*(s[to[x+1]]-s[x]);
			if(a[x]) ans[top]+=s[to[x+1]]-s[to[x-1]-1]-1;
			int l=to[x-1],r=to[x+1];
			to[l]=r;to[r]=l;
		}
//		cerr<<ans[top]<<endl;
	}
	void undo(int cnt){
//		cerr<<"undo "<<cnt<<endl;
		while(cnt--){
			int x=stk[top];
			--top;
			if(to[x-1]){
				if(to[x-1]<x) to[to[x-1]]=x-1;
				else to[x-1]=x-1;
			}
			if(to[x+1]){
				if(to[x+1]>x) to[to[x+1]]=x+1;
				else to[x+1]=x+1;
			}
			to[x]=b[x]=0;
		}
	}
	void reset(){undo(top);}
	unsigned long long ask(){return ans[top];}
};
int N;
struct FFT{
	int n,Q,m,BB;
	int a[500005];
	Query q[500005];
	unsigned long long ans[500005];
	int oc[500005][3],R[500005];
	set<int> se;
	vector<int> qr[500005];
	int imp[500005];
	int lb[500005];
	List ls;
	void clear(){se.clear();for(int i=1;i<=m;++i)R[imp[i]]=-1;for(int i=1;i*BB-BB+1<=n;++i)qr[i].clear();ls.clear(n);n=Q=0;}
	void push_back(int x,int y){a[++n]=y;se.insert(x);oc[x][++R[x]]=n;if(R[x]>=1)assert(0);}
	void add_query(Query qq){q[++Q]=qq;}
	void run(){
//		cerr<<"run\n";
		ls.geta(a,n);
		m=0;
		for(int i=1;i<=N+1;++i) lb[i]=0;
		for(auto x:se) imp[lb[x]=++m]=x;
		BB=0.7*m/sqrt(Q);
		if(BB==0) BB=1;
		for(int i=N+1,lst=m+1;i;--i){
			if(lb[i]) lst=lb[i];
			else lb[i]=lst;
		}
		for(int i=1;i<=Q;++i){
			q[i].l=lb[q[i].l];
			q[i].r=lb[q[i].r+1]-1;
			if(q[i].l<=q[i].r){
				if((q[i].l-1)/BB==(q[i].r-1)/BB){
					ls.reset();
					for(int j=q[i].l;j<=q[i].r;++j)
						for(int k=0;k<=R[imp[j]];++k) ls.insert(oc[imp[j]][k]);
					ans[q[i].id]+=ls.ask();
//					cerr<<"ans="<<ans[i]<<endl;
				}else qr[(q[i].l-1)/BB+1].push_back(i);
			}
		}
//		cerr<<"--------\n";
		for(int i=1;i*BB-BB+1<=n;++i){
			if(qr[i].empty()) continue;
			ls.reset();
			int L=i*BB+1,l=i*BB+1,r=i*BB;
			for(auto qi:qr[i]){
				while(r<q[qi].r){
					++r;
					for(int k=0;k<=R[imp[r]];++k) ls.insert(oc[imp[r]][k]);
				}
				int cnt=0;
				while(l>q[qi].l){
					--l;
					for(int k=0;k<=R[imp[l]];++k) ls.insert(oc[imp[l]][k]),++cnt;
				}
				ans[q[qi].id]+=ls.ask();
				ls.undo(cnt);
				l=L;
			}
		}
	}
};
int n,Q;
int a[500005],p[500005];
int cnt[500005];
vector<int> oc[500005];
vector<int> vc[500005];
vector<int> qr[500005];
int mn[20][500005],mx[20][500005];
Query q[500005];
unsigned long long ans[500005];
int lg2[500005];
NTT ntt1;
FFT fft1;
int askMn(int l,int r){
	int len=__lg(r-l+1);
	return min(mn[len][l],mn[len][r-(1<<len)+1]);
}
int askMx(int l,int r){
	int len=__lg(r-l+1);
	return max(mx[len][l],mx[len][r-(1<<len)+1]);
}
signed main(){
	n=read();Q=read();
	N=n;
	lg2[0]=-1;
	for(int i=1;i<=n;++i) lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<=n;++i) F[i]=(unsigned long long)i*(i-1)/2;
	for(int i=1;i<=n;++i) a[i]=read(),++cnt[a[i]],oc[a[i]].push_back(i);
	for(int i=1;i<=n;++i) p[i]=read(),mn[0][i]=mx[0][i]=p[i];
	for(int i=1;i<=Q;++i) q[i].id=i,q[i].l=read(),q[i].r=read();
	sort(q+1,q+Q+1,[&](Query x,Query y){return x.r<y.r;});
	for(int i=1;i<=Q;++i) qr[q[i].r].push_back(i);
	for(int i=1;i<20;++i)
		for(int j=1;j+(1<<i)-1<=n;++j){
			mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
			mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
		}
	for(int i=1;i<=n;++i){
//		cerr<<"i="<<i<<endl;
		sort(oc[i].begin(),oc[i].end());
		if(cnt[i]<=B){
			for(int j=0;j+1<cnt[i];++j){
				for(int k=j+1;k<cnt[i];++k){
					int l=askMn(oc[i][j],oc[i][k]);
					int r=askMx(oc[i][j],oc[i][k]);
					vc[r].push_back(l);
				}
			}
		}else{
			fft1.clear();
			for(int j=0;j<cnt[i];++j){
				fft1.push_back(p[oc[i][j]],1);
				if(j+1!=cnt[i]){
					if(oc[i][j]+1!=oc[i][j+1]){
						int l=askMn(oc[i][j]+1,oc[i][j+1]-1);
						int r=askMx(oc[i][j]+1,oc[i][j+1]-1);
						fft1.push_back(l,0);
						if(r!=l) fft1.push_back(r,0);
					}
				}
			}
			for(int j=1;j<=Q;++j) fft1.add_query(q[j]);
			fft1.run();
		}
	}
	for(int j=1;j<=Q;++j) ans[j]=fft1.ans[j];
	for(int i=1;i<=n;++i){
		for(int x:vc[i]) ntt1.add(x);
		for(int qi:qr[i]) ans[q[qi].id]+=ntt1.ask(q[qi].l,i);
	}
	for(int i=1;i<=Q;++i) write(ans[i]);
	return flush(),0;
}