#include<bits/stdc++.h>
#define lowbit(x) (x)&(-x)
#define int long long
using namespace std;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}
const int N=5e5+19;
int t[2*N],l,r;
int n,m;
int a[N],b[N],d[N];
struct lwr{
	int l,r,id;
}op[2*N];
int ans[N];
int s[2*N],s1[2*N],s2[2*N],top;
bool cmp(lwr x,lwr y){return x.r<=y.r;}
int ask(int x)
{
	int res=0;
	while(x)
	{
		res+=t[x];
		x-=lowbit(x);	
	}	
	return res;
} 
void add(int x,int v)
{
	while(x<=n)
	{
		t[x]+=v;
		x+=lowbit(x);
	}
}
signed main()
{
//	freopen("1.txt","r",stdin);
	top=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=n;i++)
	{
		int x=a[i],y=b[i];
		if(!top){s[++top]=x;s1[top]=y;s2[top]=i;d[i]=0;}
		else{
			while(top)
			{
				int xx=s[top],yy=s1[top];
               	if(xx!=x&&yy>y){d[i]=s2[top];s[++top]=x;s1[top]=y;s2[top]=i;break;}
               	else top--;
			}
          	if(!top){s[++top]=x;s1[top]=y;s2[top]=i;d[i]=0;}
		}
	} 	 
//	for(int i=1;i<=n;i++)cout<<d[i]<<" ";
	for(int i=1;i<=m;i++)
	{
			op[i].l=read();op[i].r=read();
			op[i].id=i;
	}
	sort(op+1,op+1+m,cmp);
	op[0].r=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=op[i-1].r+1;j<=op[i].r;j++)
			add(d[j]+1,1);
		ans[op[i].id]=ask(op[i].l)-op[i].l+1;
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
}