#include<iostream>
#include<stack>
#include<cstdio>
using namespace std;
const int N=5e5+5;
int a[N],b[N];
int d[N];

#define mid ((l+r)/2)
int sum[40*N],lc[40*N],rc[40*N],rt[N],cnt=0;
void build(int &u,int l,int r){
    u=++cnt;
    if(l==r){
        sum[u]=0;
        return;
    }
    build(lc[u],l,mid);
    build(rc[u],mid+1,r);
    sum[u]=sum[lc[u]]+sum[rc[u]];
}
void update(int &u,int p,int l,int r,int pos,int v){
    u=++cnt;
    sum[u]=sum[p];
    lc[u]=lc[p];rc[u]=rc[p];
    if(l==r){
        sum[u]+=v;
        return;
    }
    if(pos<=mid) update(lc[u],lc[p],l,mid,pos,v);
    else update(rc[u],rc[p],mid+1,r,pos,v);
    sum[u]=sum[lc[u]]+sum[rc[u]];
}
int query(int u,int l,int r,int xl,int xr){
    if(xl<=l&&r<=xr){
        return sum[u];
    }
    int ans=0;
    if(xl<=mid) ans+=query(lc[u],l,mid,xl,xr);
    if(mid+1<=xr) ans+=query(rc[u],mid+1,r,xl,xr);
    return ans;
}
int st[N];
int 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;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    int t=0;
    for(int i=1;i<=n;i++){
        while(t){
            int now=st[t];
            if(!t||(a[now]!=a[i]&&b[i]<b[now])) break;
            t--;
        }
        if(!t) d[i]=0;
        else d[i]=st[t];
        st[++t]=i;
    }
//    stack<int>st;
//    for(int i=1;i<=n;i++){
//        while(!st.empty()){
//            int now=st.top();
//            if(st.empty()||(a[now]!=a[i]&&b[i]<b[now])) break;
//            st.pop();
//        }
//        if(st.empty()) d[i]=0;
//        else d[i]=st.top();
//        st.push(i);
////        cout<<d[i]<<" ";
//    }
//    cout<<endl;
    build(rt[0],0,n);
    for(int i=1;i<=n;i++){
        update(rt[i],rt[i-1],0,n,d[i],1);
    }
    while(q--){
        int l,r;
        cin>>l>>r; 
//        int ans=0;
//        for(int i=l;i<=r;i++){
//            if(d[i]<l) ans++;
//        }
//        cout<<ans<<endl;
        cout<<query(rt[r],0,n,0,l-1)-query(rt[l-1],0,n,0,l-1)<<'\n';
//        cout<<"!"<<query(rt[r],0,n,0,l-1)<<" "<<query(rt[l-1],0,n,0,l-1)<<endl;
    }
//    cout<<"!"<<d[10];
    return 0;
}