#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],b[100001],cnt,q;
stack<int>st1;
stack<int>st2;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    
    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++)
        if(b[i]==n-i+1)
            cnt++;
    if(cnt==n){
        while(q--){
            int l,r,ans=0,tot=1; 
            cin>>l>>r;
            for(int i=l;i<=r-1;i++){
                if(a[i]!=a[i+1])
                    tot++;
                else
                    tot--;
                if(tot==0)
                    ans++;  
            }
            cout<<ans<<endl;
        }
        return 0;
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        stack<pair<int, int>>st;
        int ans=0;
        for(int i=l;i<=r;i++){
            while(!st.empty()){
                int pa=st.top().first;
                int pb=st.top().second;
                if(pb<=b[i]||a[i]==pa){
                    st.pop();
                    
                }
                else
                    break;
            }
            st.push({a[i],b[i]});
            if(st.size()==1)
                ans++; 
        }
        cout<<ans<<endl;
        /*int l,r,ans=0;
        cin>>l>>r;
        st1.push(a[l]),st2.push(b[l]);
        ans++;
        for(int i=l+1;i<=r;i++){
            cout<<st1.top()<<" "<<st2.top();
            while((a[i]==st1.top()||b[i]>=st2.top())&&(!st2.empty())){
                st1.pop();
                st2.pop();
                
            }
           
            st1.push(a[i]);
            st2.push(b[i]);
            if(st1.size()==1)
                ans++;
        }
        cout<<ans<<endl;*/
    }    
    return 0;
        
    
    
}