#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[500500],b[500500];
int f[500005];

signed main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n,q;
    int pan1=0,pan2=0;
    cin>>n>>q;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=i)pan1=1;
        
        
        
    }
    for(int i = n;i>=1;i--){
        if(a[i]==a[i+1])f[i]=f[i+1]+1;
        else f[i]=1;
    }
    for(int i = 1;i<=n;i++){
        cin>>b[i];
        if(b[i]!=n-i+1)pan2=1;
    }
    
    if(n<=1000 && q<=1000){
        
        for(int i = 1;i<=q;i++){
            int l,r;
            cin>>l>>r;
            stack<int> aa;
            stack<int> bb;
            int ans=0;
            for(int j = l;j<=r;j++){
                if(aa.size()==0){
                    aa.push(a[j]);
                    bb.push(b[j]);
                    
                    
                    
                }
                else{
                    while(aa.size()!=0){
                        if(aa.top()==a[j] || bb.top()<=b[j]){
                            aa.pop(),bb.pop();
                        }
                        else break;
                        
                        
                    }
                    aa.push(a[j]),bb.push(b[j]);
                    
                    
                    
                }
                
                
                
                
                
                
                
                if(aa.size()==1)ans++;
            }
            cout<<ans<<endl;
        }
        return 0;
    }
    if(pan1==0){
        for(int i = 1;i<=n;i++){
            if(b[i]>=b[i-1]){
                f[i]=f[i-1]+1;
            }
            else f[i]=f[i-1];
        }
        for(int i =1;i<=q;i++){
            int l,r;
            cin>>l>>r;
            cout<<f[r]-f[l-1]<<endl;
        }
        
        
        
    }
    if(pan2==0){
        for(int i = 1;i<=q;i++){
            int l,r;
            cin>>l>>r;
            cout<<min(f[l],r)<<endl;
        }
    }
    
    
    return 0;
}