#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (int)(1e18)
#define pr pair<int,int>

const int N=5e5+10; 

int n,q;
int a[N],b[N];

inline int read(){
    int t=0,f=1;
    register char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?(-1):(f),c=getchar();
    while(c>='0'&&c<='9') t=(t<<3)+(t<<1)+(c^48),c=getchar();
    return t*f;
}

stack<int> s;

vector<int> g[N];
vector<pr> Q[N];

int ans[N];

struct Tree{
    #define mid (l+r>>1)
    
    int tr[N<<2];
    
    void update(int p,int l,int r,int x){
        if(l==r) return (void)(tr[p]++);
        if(x<=mid) update(p<<1,l,mid,x);
        else update(p<<1|1,mid+1,r,x);
        tr[p]=tr[p<<1]+tr[p<<1|1];
    }
    
    int query(int p,int l,int r,int L,int R){
        if(L<=l&&R>=r) return tr[p];
        int res=0;
        if(L<=mid) res+=query(p<<1,l,mid,L,R);
        if(R>mid) res+=query(p<<1|1,mid+1,r,L,R);
        return res;
    }

    #undef mid
}Tr;

signed main(){
    freopen("stack.in","r",stdin);
    freopen("stack.out","w",stdout);
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    b[0]=INT_MAX;s.push(0); 
    for(int i=1;i<=n;i++){
        while(!(a[s.top()]!=a[i]&&b[s.top()]>b[i])) s.pop();
        g[s.top()].push_back(i),s.push(i);
    }
    for(int i=1;i<=q;i++){
        int l=read(),r=read();
        Q[l].push_back({r,i});
    }
    for(int i=0;i<=n;i++){
        for(pr j:Q[i]) ans[j.second]=Tr.query(1,1,n,i,j.first);
        for(int j:g[i]) Tr.update(1,1,n,j);
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
    return 0;
}