#include<bits/stdc++.h>
using namespace std;

// #define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define all(_array) (_array).begin(),(_array).end()
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define TAK cout<<"TAK"<<endl
#define NIE cout<<"NIE"<<endl
#define OK cerr<<"OK"<<endl
#define pii pair<int,int>
#define endl '\n'

bool bg_memory;
const int mod=1e9+7;
const int inf=2147483647;
const int bs=233;
const double eps=1e-6;
const int N=5e5+7;
template<class _t1,class _t2>inline void cmax(_t1 &a,_t2 b){a=a<b?b:a;}
template<class _t1,class _t2>inline void cmin(_t1 &a,_t2 b){a=a>b?b:a;}
inline int qp(int a,int b){int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;}
inline int sqrt(int x,int r){int l=0,ans=0;while(l<=r){if(1ll*mid*mid<=x) ans=mid,l=mid+1;else r=mid-1;}return ans;}

int n,m,b,l,r,bbl;
int L[N],R[N],tl[N],tr[N],p[N];
int a[N],y[N];
int mn[N][19],mx[N][19];
int lg[N];
int ap[N];
vector<int> vd[N];
int cnt;
inline int gmin(int x,int y){return min(mn[x][lg[y-x+1]],mn[y-(1<<lg[y-x+1])+1][lg[y-x+1]]);}
inline int gmax(int x,int y){return max(mx[x][lg[y-x+1]],mx[y-(1<<lg[y-x+1])+1][lg[y-x+1]]);}
vector<pair<pii,pii>> add[N];
int val[N],bl[710],onbl[N],bgbl[710],enbl[710],bsz;
vector<pii> q[N];
long long ans[N];
int nm[N],nt,pos[N];
int tsl[N],tsr[N];
int o[N],ont;
bool on[N];
struct dsu{
    int to[N],cnt[N],sum;
    stack<pair<pii,int>> st;
    inline void flsh(){
        while(st.size()) st.pop();
        sum=0;
        for(int i=1;i<=nt+1;i++) to[i]=cnt[i]=0;
    }
    inline void reverse(){
        while(st.size()){
            int x=st.top().first.first;
            int y=st.top().first.second;
            int z=st.top().second;
            st.pop();
            to[z]=x;
            cnt[z]=y;
        }
    }
}dsu;
inline void addin(int x,bool p){
    o[++ont]=x;
    nm[++nt]=x,on[nt]=p;
}
inline void ad(int x,int o){
    int l=pos[x],r=pos[x];
    int val=on[pos[x]];
    if(dsu.to[pos[x]+1]){
        r=dsu.to[pos[x]+1];
        dsu.sum-=dsu.cnt[pos[x]+1]*(dsu.cnt[pos[x]+1]-1)/2;
        val+=dsu.cnt[pos[x]+1];
    }
    if(dsu.to[pos[x]-1]){
        l=dsu.to[pos[x]-1];
        dsu.sum-=dsu.cnt[l]*(dsu.cnt[l]-1)/2;
        val+=dsu.cnt[l];
    }
    dsu.sum+=val*(val-1)/2;
    if(o) dsu.st.push({{dsu.to[l],dsu.cnt[l]},l});
    dsu.to[l]=r,dsu.cnt[l]=val;
    if(o) dsu.st.push({{dsu.to[r],dsu.cnt[r]},r});
    dsu.to[r]=l;
}
inline void upd(int i,int x){
    l=x;
    while(r<tr[i]) ad(++r,0);
    int tmp=dsu.sum;
    while(l>tl[i]) ad(--l,1);
    ans[i]+=dsu.sum;
    dsu.reverse();
    dsu.sum=tmp;
}

mt19937 rnd(time(0));
int Case=1;
void Main(){
    
    cin>>n>>m;
    b=12000;
    bsz=sqrt(n);
    for(int i=1;i<=m;i++) tsl[i]=tsr[i]=i;
    for(int i=1;i<=n;i++) cin>>a[i],ap[a[i]]++;
    for(int i=1;i<=n;i++) cin>>y[i],mn[i][0]=mx[i][0]=y[i];
    for(int i=1;i<=m;i++) cin>>L[i]>>R[i],q[R[i]].push_back({L[i],i});
    sort(tsl+1,tsl+m+1,[](int a,int b){return L[a]<L[b];});
    sort(tsr+1,tsr+m+1,[](int a,int b){return R[a]<R[b];});
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<19;i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            mn[j][i]=min(mn[j][i-1],mn[j+(1<<i-1)][i-1]);
            mx[j][i]=max(mx[j][i-1],mx[j+(1<<i-1)][i-1]);
        }
    }
    for(int i=1,j=1,k=1;i<=n;i++,j++){
        onbl[i]=k;
        if(j==1) bgbl[k]=i;
        if(j==bsz||i==n) enbl[k]=i,j=0,k++;
    }
    for(int i=1;i<=n;i++){
        if(ap[a[i]]<=b){
            if(vd[a[i]].size()){
                int tmp=gmax(vd[a[i]].back(),i),tl,tr;
                l=0,r=vd[a[i]].size()-1;
                while(l<=r){
                    if(gmax(vd[a[i]][mid],i)==tmp) tl=mid,r=mid-1;
                    else l=mid+1;
                }
                if(y[vd[a[i]].back()]==tmp) tl=vd[a[i]].size()-1;
                l=i,r=n;
                while(l<=r){
                    if(gmax(vd[a[i]].back(),mid)==tmp) tr=mid,l=mid+1;
                    else r=mid-1;
                }
                add[tmp].push_back({{tl,vd[a[i]].size()-1},{a[i],tr}});
            }    
        }
        vd[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        for(pair<pii,pii> j:add[i]){
            for(int k=j.first.first;k<=j.first.second;k++){
                for(int o=j.first.second+1;o<vd[j.second.first].size();o++){
                    if(vd[j.second.first][o]>j.second.second) break;
                    int tmp=gmin(vd[j.second.first][k],vd[j.second.first][o]);
                    val[tmp]++,bl[onbl[tmp]]++;
                }
            }
        }
        for(pii j:q[i]){
            if(onbl[j.first]==onbl[i]){
                for(int k=j.first;k<=i;k++) ans[j.second]+=val[k];
            }else{
                for(int k=j.first;k<=enbl[onbl[j.first]];k++) ans[j.second]+=val[k];
                for(int k=onbl[j.first]+1;k<onbl[i];k++) ans[j.second]+=bl[k];
                for(int k=bgbl[onbl[i]];k<=i;k++) ans[j.second]+=val[k];    
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(ap[i]<=b) continue;
        int mx=0,mn=inf;
        nt=ont=0;
        for(int j=1;j<=n;j++){
            if(a[j]==i&&a[j-1]!=i){
                addin(mx,0);
                if(mx!=mn) addin(mn,0);
                addin(y[j],1);
                mx=0,mn=inf;
            }else if(a[j]==i&&a[j-1]==i){
                addin(y[j],1);
                mx=0,mn=inf;
            }else cmax(mx,y[j]),cmin(mn,y[j]);
        }
        bbl=ceil(1.0*nt/sqrt(m));
        sort(o+1,o+ont+1);
        for(int j=1;j<=nt;j++) nm[j]=lower_bound(o+1,o+ont+1,nm[j])-o,pos[nm[j]]=j;
        int tml=1,tmr=ont;
        for(int j=1;j<=m;j++){
            while(tml<=ont&&L[tsl[j]]>o[tml]) tml++;
            tl[tsl[j]]=tml;
            p[j]=j;
        }
        for(int j=m;j>=1;j--){
            while(tmr>=1&&R[tsr[j]]<o[tmr]) tmr--;
            tr[tsr[j]]=tmr;
        }
        sort(p+1,p+m+1,[](int a,int b){return tl[a]/bbl!=tl[b]/bbl?tl[a]/bbl<tl[b]/bbl:tr[a]<tr[b];});
        int cur_bl=-1;
        l=r=0;
        dsu.flsh();
        for(int j=1;j<=m;j++){
            if(tl[p[j]]>tr[p[j]]) continue;
            if(tl[p[j]]>ont) continue;
            if(tl[p[j]]/bbl!=cur_bl){
                cur_bl=tl[p[j]]/bbl;
                l=min(n+1,(cur_bl+1)*bbl);
                r=min(n,(cur_bl+1)*bbl-1);
                dsu.flsh();
            }
            if(tl[p[j]]/bbl==tr[p[j]]/bbl){
                for(int k=tl[p[j]];k<=tr[p[j]];k++) ad(k,1);
                ans[p[j]]+=dsu.sum;
                dsu.reverse();
                continue;
            }
            upd(p[j],min(n+1,(cur_bl+1)*bbl));
        }
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;

    return;
}
string RdFile="";
bool en_memory;

signed main(){
    auto bg_clock=chrono::high_resolution_clock::now();
    // freopen((RdFile+".in").c_str(),"r",stdin);
    // freopen((RdFile+".out").c_str(),"w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // cin>>Case;
    while(Case--) Main();
    auto en_clock=chrono::high_resolution_clock::now();
    auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
    double duration_count=duration_clock.count()*0.001;
    double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
    // cerr<<"Time:"<<duration_count<<"ms"<<endl;
    // cerr<<"Memory: "<<memory_used<<"MB"<<endl;
    return 0;
}