#include <bits/stdc++.h>
using namespace std;
int read()
{
    int res=0,c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar()) res=res*10+(c^48);
    return res;
}
int n,m;
int val1[500010],val2[500010];
struct state
{
    int a,b,idx;
    state(int _a,int _b,int _idx) : a(_a),b(_b),idx(_idx){}
    state(){}
};
stack<state>st;
int root[500010];
int sum[10000050],ls[10000050],rs[10000050],cnt;
void insert(int last,int now,int l,int r,int pos,int v)
{
    sum[now]=sum[last]+v;
    if(l==r) return;
    ls[now]=ls[last]; rs[now]=rs[last];
    int mid=(l+r)>>1;
    if(pos<=mid)
    {
        ls[now]=++cnt;
        insert(ls[last],ls[now],l,mid,pos,v);
    }
    else
    {
        rs[now]=++cnt;
        insert(rs[last],rs[now],mid+1,r,pos,v);
    }
}
int query(int rt1,int rt2,int l,int r,int pl,int pr)
{
    if(l>=pl&&r<=pr) return sum[rt2]-sum[rt1];
    int mid=(l+r)>>1;
    if(pl<=mid)
    {
        if(pr>mid) return query(ls[rt1],ls[rt2],l,mid,pl,pr)+query(rs[rt1],rs[rt2],mid+1,r,pl,pr);
        else return query(ls[rt1],ls[rt2],l,mid,pl,pr);
    }
    else return query(rs[rt1],rs[rt2],mid+1,r,pl,pr);
}
int main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++) val1[i]=read();
    for(int i=1;i<=n;i++) val2[i]=read();
    for(int i=1;i<=n;i++)
    {
        while(st.size()&&(st.top().a==val1[i]||st.top().b<=val2[i])) st.pop();
        root[i]=++cnt;
        insert(root[i-1],root[i],1,n+1,(st.size()?st.top().idx:n+1),1);
        st.emplace(val1[i],val2[i],i);
    }
    while(m--)
    {
        int l,r;
        l=read(); r=read();
        printf("%d\n",r-l+1-query(root[l-1],root[r],1,n+1,l,r));
    }
    return 0;
}