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

ll n,Q;
ll a[510000],b[510000];
ll c[510000];
ll st[510000];
ll f[30][510000];
ll cnt;

int main(){
	freopen("stack.in","r",stdin);
	freopen("stack.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>Q;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	for (int i=1;i<=n;i++){
		cin>>b[i];
	}
	for (int i=1;i<=n;i++){
		while (cnt>0){
			ll j=st[cnt];
			if (a[i]==a[j]||b[i]>=b[j]){
				c[j]=i;
				cnt--;
			}else break;
		}
		st[++cnt]=i;
	}
	while (cnt>0){
		c[st[cnt--]]=n+1;
	}
	c[n+1]=n+1;
	for (int i=1;i<=n+1;i++){
		f[0][i]=c[i];
	}
	for (int k=1;k<20;k++){
		for (int i=1;i<=n+1;i++){
			f[k][i]=f[k-1][f[k-1][i]];
		}
	}
	while (Q--){
		ll l,r;
		cin>>l>>r;
		ll ans=1;
		ll tot=l;
		for (int k=19;k>=0;k--){
			if (f[k][tot]<=r){
				ans+=(1<<k);
				tot=f[k][tot];
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}