#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=500010;

struct tree{
    int l,r,id;
    bool operator<(const tree&x)const{return r<x.r;}
}Q[MAXN];
int n,q,pos=1;
int a[MAXN],b[MAXN],c[MAXN],ans[MAXN];
stack<int> st;

int lowbit(int x){return x&-x;}
void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=c[i];
    return res;
}

int main()
{
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=q;i++)
    {
        cin>>Q[i].l>>Q[i].r;
        Q[i].id=i;
    }
    sort(Q+1,Q+q+1);
    a[0]=b[0]=INF;
    st.push(0);
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            int j=st.top();
            if(a[i]!=a[j]&&b[i]<b[j]) break;
            st.pop();
        }
        add(st.top()+1,1);
        add(i+1,-1);
        st.push(i);
        while(Q[pos].r==i)
        {
            ans[Q[pos].id]=sum(Q[pos].l);
            pos++;
        }
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}