#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,q,a[N],b[N],pre[N],mk[N],f,s[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.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];
        if(a[i]!=i)f=1;
    }
    for(int i=1;i<=n;i++)cin>>b[i];
//    if(!f){
        
//    }
//    else{
        for(int i=1;i<=n;i++){
            for(int j=i-1;j>=1;j--){
                if(a[j]!=a[i]&&b[j]>b[i]){
                    pre[i]=j;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            s[i]=s[i-1];
            if(!pre[i])mk[i]=1;
            if(s[i]-s[pre[i]]>0)mk[i]=1;
            s[i]+=mk[i];
        }
        while(q--){
            int l,r,cnt=0;;
            cin>>l>>r;
            for(int i=l;i<=r;i++){
                if(pre[i]<l||mk[i])cnt++;
            }
            cout<<cnt<<"\n";
        }
//    }
//    while(q--){
//        int l,r;
//        cin>>l>>r;
//        cout<<query(l,r)<<"\n";
//    }
    return 0;
}
/*
10 4
3 1 3 1 2 3 3 2 1 1
10 10 2 9 7 5 4 7 6 1
1 4
7 8
7 10
1 8
*/