#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10; 
int n,m;
int f[N],a[N],b[N],ff[N];
stack<int> st;
void solve1(){
    int cnt=0;
    b[0]=INT_MAX;
    for(int i=1;i<=n;i++){
        if(b[i]<b[i-1]) f[i]=++cnt;
        else f[i]=cnt;
    }
    int l,r;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        
    }
}
void solve2(){
    a[0]=-1;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1];
        if(a[i]!=a[i-1]) f[i]++,ff[f[i]]=i;
    }
    int l,r;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        if(f[l]==f[r]) cout<<r-l+1<<'\n';
        else cout<<ff[f[l]+1]-l<<'\n';
    }
}
signed main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	int p1=0,p2=0;
    for(int i=1;i<=n;i++){
	    if(b[i]!=n-i+1) p1=1;
	    if(a[i]!=i) p2=1;
    }
    if(p2==0){
        solve1();
        return 0;
    }
    if(p1==0){
        solve2();
        return 0;
    }
    int l,r;
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        int cnt=0;
        while(!st.empty()) st.pop(); 
        for(int j=l;j<=r;j++){
            while(!st.empty()&&(a[st.top()]==a[j]||b[st.top()]<=b[j])) 
                st.pop();
            if(st.empty()) cnt++;
            st.push(j);
        }
        cout<<cnt<<endl;
    }
	return 0;
}