#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll a[500005],b[21][500005],c[21][500005],lg[500005],ans[500005],n,m;
struct qry {
	ll l,r,id;
} p[500005],p2[500005];
vector<ll> col[500005],CC[500005];
const ll S=600;
ll S2=0;

struct block {
	const ll B=600;
	ll tag[805],z[500005];
	void add(ll pos,ll v) {
		z[pos]+=v;
		tag[(pos-1)/B+1]+=v;
	}
	ll query(ll pos) {
		ll v=(pos-1)/B+1,r=(n-1)/B+1,ans=0;
		for (ll i=v+1; i<=r; i++)ans+=tag[i];
		for (ll i=pos; i<=v*B; i++)ans+=z[i];
		return ans;
	}
} B;

ll getmx(ll l,ll r) {
	ll k=lg[r-l+1];
	return max(c[k][l],c[k][r-(1ll<<k)+1]);
}

ll getmi(ll l,ll r) {
	ll k=lg[r-l+1];
	return min(b[k][l],b[k][r-(1ll<<k)+1]);
}

ll v[1000005],cnt[1000005],d[1000005],nxt[1000005],to[1000005],T;
vector<qry> Q[1000005];

struct CHAIN{
	ll vis[1000005],sz[1000005],ano[1000005];
	array<ll,5> stk[1000005];
	ll top,gx;
	void init(ll len){
		for (ll i=0;i<=len;i++)vis[i]=0,sz[i]=1,ano[i]=i;
		top=0,gx=0;
	}
	
	void link(ll a){
		ll l=ano[a],r=ano[a+1];
		ano[l]=r,ano[r]=l;
		stk[++top]={l,r,a,sz[a],sz[a+1]};
		gx+=sz[a]*sz[a+1];
		sz[l]=sz[r]=sz[a]+sz[a+1];
//		cout<<"?" <<a<<" "<< sz[a]<<" "<<sz[a+1]<<"\n";
		
	}
	
	void add(ll pos){
		vis[d[pos]]++;
		if (vis[d[pos]]==2){
			link(d[pos]);
		}
	}
	void del(ll pos){
		vis[d[pos]]--;
		if (vis[d[pos]]==1){
			redo();
		}
	}
	void redo(){
		auto tp=stk[top--];
		gx-=tp[3]*tp[4];
		ano[tp[0]]=tp[2];
		ano[tp[1]]=tp[2]+1;
		sz[tp[0]]=tp[3];
		sz[tp[1]]=tp[4];
	}
}C;

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (ll i=1; i<=n; i++) {
		cin >> a[i];
		col[a[i]].push_back(i);
	}
	for (ll i=1; i<=n; i++) {
		if (i>1)lg[i]=lg[i>>1]+1;
		cin >> b[0][i];
		c[0][i]=b[0][i];
	}
	for (ll i=1; i<=20; i++) {
		for (ll j=1; j+(1ll<<i)-1<=n; j++) {
			b[i][j]=min(b[i-1][j],b[i-1][j+(1ll<<(i-1))]);
			c[i][j]=max(c[i-1][j],c[i-1][j+(1ll<<(i-1))]);
		}
	}
	for (ll i=1; i<=m; i++) {
		cin >> p[i].l >> p[i].r;
		p[i].id=i;
	}
	for (ll i=1; i<=n; i++) {
		if (col[i].size()<=S) {
			for (ll j=0; j<(ll)col[i].size(); j++) {
				for (ll k=j+1; k<(ll)col[i].size(); k++) {
					ll mi=getmi(col[i][j],col[i][k]),mx=getmx(col[i][j],col[i][k]);
					CC[mx].push_back(mi);
				}
			}
		}
	}
	sort(p+1,p+1+m,[](qry a,qry b) {
		return a.r<b.r;
	});
	ll ps=0;
	for (ll i=1; i<=m; i++) {
		while (ps+1<=n&&ps+1<=p[i].r) {
			for (ll j:CC[ps+1]) {
				B.add(j,1);
			}
			ps++;
		}
		ans[p[i].id]+=B.query(p[i].l);
	}
	for (ll i=1; i<=n; i++) {
		if (col[i].size()>S) {
			T=i;
			ll N=col[i].size();
			vector<ll> book;
			for (ll j=0; j+1<N; j++) {
				ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
				book.push_back(mi);
				book.push_back(mx);
			}
			sort(book.begin(),book.end());
			book.erase(unique(book.begin(),book.end()),book.end());
			for (ll j=0; j+1<N; j++) {
				ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
				++cnt[lower_bound(book.begin(),book.end(),mi)-book.begin()+1];
				++cnt[lower_bound(book.begin(),book.end(),mx)-book.begin()+1];
			}
			for (ll j=1; j<=(ll)book.size(); j++)cnt[j]+=cnt[j-1];
			for (ll j=0; j+1<N; j++) {
				ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
				ll mip=lower_bound(book.begin(),book.end(),mi)-book.begin()+1;
				ll mxp=lower_bound(book.begin(),book.end(),mx)-book.begin()+1;
				d[cnt[mip]--]=j;
				to[cnt[mip]+1]=mi;
				d[cnt[mxp]--]=j;
				to[cnt[mxp]+1]=mx;
			}
			ll ps=0;
			for (ll j=1; j<=n; j++) {
				while (ps+1<=2*(N-1)&&to[ps+1]<=j)ps++;
				nxt[j]=ps;
			}
			S2=2*(N-1)/sqrt(m)+1;
//			cout<<"! "<< i<<"\n";
			for (ll j=1; j<=m; j++) {
				p2[j].l=nxt[p[j].l-1]+1,p2[j].r=nxt[p[j].r],p2[j].id=p[j].id;
				if ((p2[j].l-1)/S2==(p2[j].r-1)/S2) {
					C.init(N);
					for (ll k=p2[j].l; k<=p2[j].r; k++) {
						C.add(k);
					}
					ans[p2[j].id]+=C.gx;
//					cout<< p2[j].id<<":"<<C.gx<<"\n";
				} else {
					Q[(p2[j].l-1)/S2+1].push_back(p2[j]);
				}
			}
			for (ll j=1; j<=(2*(N-1)-1)/S2+1; j++) {
				ll lb=j*S2;
				C.init(N);
				ll L=lb+1,R=lb;
				for (qry k:Q[j]) {
					while (R<k.r)C.add(++R);
					while (L>k.l)C.add(--L);
					while (L<lb+1)C.del(L++);
					ans[k.id]+=C.gx;
				}
			}
			for (ll j=1; j<=2*(N-1); j++)cnt[j]=to[j]=nxt[j]=d[j]=0,Q[j].clear();
		}
	}
	for (ll i=1; i<=m; i++) {
		cout<< ans[i]<<"\n";
	}
	return 0;
}

/*
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/