#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pir pair<int,int>
#define fi first
#define se second
using namespace std;
inline int re()
{
    char c=getchar();
    int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=500010;
int n,q;
int a[N],b[N];
int tpos[N];
int s[N],top;
vector<pir> qs[N];
int res[N];
int c[N];
void add(int w,int z)
{
    while(w<=N-5)
    {
        c[w]+=z;
        w+=w&-w; 
    }
    return;
}
int query(int w)
{
    int ans=0;
    while(w)
    {
        ans+=c[w];
        w-=w&-w;
    }
    return ans;
}
int main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    n=re();q=re();
    for(int i=1;i<=n;i++) a[i]=re();
    for(int i=1;i<=n;i++) b[i]=re();
    for(int i=1;i<=q;i++)
    {
        int l=re(),r=re();
        qs[r].pb(mp(l,i));
    }
    for(int i=1;i<=n;i++)
    {
        while(top&&(a[s[top]]==a[i]||b[s[top]]<=b[i]))
        {
            tpos[s[top]]=i;
            top--;
        }
        s[++top]=i;
    }
    for(int i=1;i<=top;i++) tpos[s[i]]=n+1;
    top=0;
    tpos[0]=n+1;s[++top]=0;
    for(int i=1;i<=n;i++)
    {
        int l=1,r=top,mid;
        while(l<r)
        {
            mid=(l+r+1)>>1;
            if(tpos[s[mid]]>i) l=mid;
            else r=mid-1;
        }
        add(s[l]+1,1);
        add(i+1,-1);
        while(top&&tpos[s[top]]<=tpos[i]) top--;
        s[++top]=i;
        for(pir tmp:qs[i]) res[tmp.se]=query(tmp.fi);
    }
    for(int i=1;i<=q;i++) printf("%d\n",res[i]);
    return 0;
}