#include <bits/stdc++.h>
#define int long long
using namespace std;
const int B=0;
const int B2=500;
struct NTT{
	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)/B2+1];
	}
	int ask(int l,int r){
		int bl=(l-1)/B2+1,br=(r-1)/B2+1;
		int res=0;
		if(bl==br){
			for(int i=l;i<=r;++i) res+=a[i];
		}else{
			for(int i=l;i<=bl*B2;++i) res+=a[i];
			for(int i=bl+1;i<br;++i) res+=s[i];
			for(int i=br*B2-B2+1;i<=r;++i) res+=a[i];
		}
		return res;
	}
};
struct Query{
	int l,r,id;
	Query(){}
	Query(int a,int b,int c){l=a;r=b;id=c;}
};
int F(int x){return x*(x-1)/2;}
struct List{
	int a[500005];
	int s[500005];
	bool b[500005];
	int to[500005];
	int top,tim;
	array<int,4> stk[2500005];
	int ans[2500005];
	void clear(){memset(b,0,sizeof(b));memset(to,0,sizeof(to));top=tim=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;
		++tim;
		ans[tim]=ans[tim-1];
		stk[++top]={tim,1,x,0};b[x]=1;
		if(!b[x-1]&&!b[x+1]){
			stk[++top]={tim,2,x,0};to[x]=x;
			return;
		}
		if(!b[x-1]){
			ans[tim]-=F(s[to[x+1]]-s[x]);
			stk[++top]={tim,2,x,to[x]};to[x]=to[x+1];
			stk[++top]={tim,2,x+1,to[x+1]};to[x+1]=0;
			stk[++top]={tim,2,to[x],x+1};to[to[x]]=x;
			ans[tim]+=F(s[to[x]]-s[x-1]);
		}else if(!b[x+1]){
			ans[tim]-=F(s[x-1]-s[to[x-1]-1]);
			stk[++top]={tim,2,x,to[x]};to[x]=to[x-1];
			stk[++top]={tim,2,x-1,to[x-1]};to[x-1]=0;
			stk[++top]={tim,2,to[x],x-1};to[to[x]]=x;
			ans[tim]+=F(s[x]-s[to[x]-1]);
		}else{
			ans[tim]-=F(s[x-1]-s[to[x-1]-1]);
			ans[tim]-=F(s[to[x+1]]-s[x]);
			ans[tim]+=F(s[to[x+1]]-s[to[x-1]-1]);
			stk[++top]={tim,2,to[x-1],x-1};to[to[x-1]]=to[x+1];
			stk[++top]={tim,2,to[x+1],x+1};to[to[x+1]]=to[x-1];
			stk[++top]={tim,2,x-1,to[x-1]};to[x-1]=0;
			stk[++top]={tim,2,x+1,to[x+1]};to[x+1]=0;
		}
	}
	void undo(int cnt){
//		cerr<<"undo "<<cnt<<endl;
		tim=max(0ll,tim-cnt);
		while(top&&stk[top][0]>tim){
			if(stk[top][1]==1) b[stk[top][2]]=stk[top][3];
			else to[stk[top][2]]=stk[top][3];
			--top;
		}
	}
	void reset(){undo(tim);}
	int ask(){return ans[tim];}
};
struct FFT{
	int n,Q,BB;
	int a[500005];
	Query q[500005];
	int ans[500005];
	vector<int> oc[500005];
	set<int> se;
	map<int,int> mp;
	vector<int> qr[500005];
	int imp[500005];
	List ls;
	void clear(){n=Q=0;se.clear();mp.clear();memset(ans,0,sizeof(ans));for(int i=1;i<=500000;++i)oc[i].clear(),qr[i].clear();ls.clear();}
	void push_back(int x,int y){a[++n]=y;se.insert(x);oc[x].push_back(n);}
	void add_query(Query qq){q[++Q]=qq;}
	void run(){
//		cerr<<"run\n";
		ls.geta(a,n);
		BB=n/sqrt(Q);
		if(BB==0) BB=1;
		BB=10000;
		int m=0;
		for(auto x:se){
			mp[x]=++m;
			imp[m]=x;
		}
		for(int i=1;i<=m;++i)
			if(imp[i]!=i) oc[i].swap(oc[imp[i]]);
		se.insert(500001);
		mp[500001]=m+1;
		for(int i=1;i<=Q;++i){
			q[i].l=mp[*se.lower_bound(q[i].l)];
			q[i].r=mp[*se.upper_bound(q[i].r)]-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) ls.insert(j);
					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 ll=i*BB,l=i*BB,r=i*BB;
			ls.insert(l);
			for(auto qi:qr[i]){
				while(r<q[qi].r) ls.insert(++r);
				while(l>q[qi].l) ls.insert(--l);
				ans[q[qi].id]=ls.ask();
				ls.undo(ll-l);
				l=ll;
			}
		}
	}
};
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];
int ans[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(){
	scanf("%lld%lld",&n,&Q);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]),++cnt[a[i]],oc[a[i]].push_back(i);
	for(int i=1;i<=n;++i) scanf("%lld",&p[i]),mn[0][i]=mx[0][i]=p[i];
	for(int i=1;i<=Q;++i) scanf("%lld%lld",&q[i].l,&q[i].r),q[i].id=i,qr[q[i].r].push_back(i);
	sort(q+1,q+Q+1,[&](Query x,Query y){return x.r<y.r;});
	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){
		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) printf("%lld\n",ans[i]);
	return 0;
}