#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iostream>
#define re register
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
	return x*f;
}
inline void print(int x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
const int M = 5e5+10;
int n,Q;
int head=1,tail=0,top;
int belong[M],pre[M],s[M],a[M],b[M],sum[M],cnt[M],ans[M];
struct query{
	int l,r,id;
	friend bool operator < (query x,query y){
		if(belong[x.l]!=belong[y.l]) return belong[x.l] < belong[y.l];
		if(belong[x.l]%2==0) return x.r > y.r;
		else return x.r < y.r;
	}
}q[M];
int siz,num;
inline int query(int x){
	int res=0;
	for(re int i(1) ; i<belong[x] ; ++i) res += sum[i];
	for(re int i(belong[x]*siz) ; i<=x ; ++i) res += cnt[i];
	return res;
}
inline void add(int x){
	cnt[pre[x]]++;
	sum[belong[pre[x]]]++;
}
inline void del(int x){
	cnt[pre[x]]--;
	sum[belong[pre[x]]]--;
}
signed main(){
	n=read(),Q=read();
	siz=sqrt(n),num=ceil((double)siz/num);
	for(re int i(1) ; i<=num ; ++i){
		for(re int j((i-1)*siz+1) ; j<=i*siz ; ++j){
			belong[j] = i;
		}
	}
	for(re int i(1) ; i<=n ; ++i) a[i] = read();
	for(re int i(1) ; i<=n ; ++i) b[i] = read();
	for(re int i(1) ; i<=n ; ++i){
		while(top>0 && !(a[i]!=a[s[top]]&&b[i]<b[s[top]])) top--;
		pre[i] = s[top]+1;
		s[++top] = i;
	}
	for(re int i(1) ; i<=Q ; ++i){
		q[i].l=read(),q[i].r=read();
		q[i].id = i;
	}
	sort(q+1,q+Q+1);
	for(re int i(1) ; i<=Q ; ++i){
		int ql=q[i].l,qr=q[i].r;
		while(head < ql) del(head++);
		while(head > ql) add(--head);
		while(tail < qr) add(++tail);
		while(tail > qr) del(tail--);
		ans[q[i].id] = query(q[i].l);
	}
	for(re int i(1) ; i<=Q ; ++i) print(ans[i]),putchar('\n');
	return 0;
}