#include<bits/stdc++.h>
using namespace std;
int n,q,a[500005],b[500005];
stack<pair<int,int> >st;
int main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    if(n<=1000&&q<=1000){
        while(q--){
            while(!st.empty())st.pop();
            int l,r,ans=0;
            scanf("%d%d",&l,&r);
            for(int i=l;i<=r;i++){
                while(!st.empty()&&(a[i]==st.top().first||b[i]>=st.top().second)){
                    st.pop();
                }
                if(st.empty())ans++;
                st.push(make_pair(a[i],b[i]));
            }
            printf("%d\n",ans);
        }
    }
    else{
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",r-l+1);
        }
    }
    return 0;
}