#include<bits/stdc++.h>
#define ll long long
#define N 1001
using namespace std;
ll n,q,l,r,ans,cnt,mp[N];
struct node{ll a,b,id;}c[N];
int main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>c[i].a;
        c[i].id=i;
    }
    for(int i=1;i<=n;i++) cin>>c[i].b;
    if(n<1001){
        while(q--){
            cin>>l>>r;
            vector<node> v(n);
            cnt=0;
            for(int i=l;i<=r;i++){
                while(cnt>0&&!(v[cnt].a!=c[i].a&&v[cnt].b>c[i].b)) cnt--;
                if(cnt==0) ans++;
                v[++cnt]=c[i];
            }
            cout<<ans<<endl;
            ans=0;
        }
    }else{
        mp[n]=1;
        for(int i=n-1;i>0;i--){
            if(c[i].a==c[i+1].a) mp[i]=mp[i+1]+1;
            else mp[i]=1;
        }
        while(q--){
            cin>>l>>r;
            cout<<min(mp[l],r-l+1)<<endl;
        }
    }
    return 0;
}