#include <bits/stdc++.h>
#define ll long long
using namespace std;
//#define fread fread_unlocked
//#define fwrite fwrite_unlocked
const int LEN=10000005;int ED1=-1;
char Buf[LEN],*OP=Buf,*ED=Buf,Buf1[LEN+2];
inline void flush(){fwrite(Buf1,1,ED1+1,stdout),ED1=-1;}
inline char gc(){return (OP==ED)?(ED=(OP=Buf)+fread(Buf,1,LEN,stdin),*OP++):(*OP++);}
inline void pc(char ch){Buf1[ED1==LEN?(flush(),ED1=0):++ED1]=ch;}
inline int read(){
int x=0;char ch=gc();
while(!isdigit(ch)) ch=gc();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();
return x;
}
inline void write(unsigned long long x){
if(x==0){pc('0');pc('\n');return;}
char ch[20];short cnt=-1;
while(x){
ch[++cnt]=(char)((x%10)^48);
x/=10;
}
for(int i=cnt;i>=0;--i) pc(ch[i]);
pc('\n');
}
const int B=800;
const int B2=1024;
const int bB=10;
struct NTT{
unsigned int a[500005],s[500005];
NTT(){memset(a,0,sizeof(a));memset(s,0,sizeof(s));}
void add(int x){
++a[x];
++s[((x-1)>>bB)+1];
}
unsigned long long ask(int l,int r){
int bl=((l-1)>>bB)+1,br=((r-1)>>bB)+1;
ll res=0;
if(bl==br){
for(int i=l;i<=r;++i) res+=a[i];
}else{
for(int i=l;i<=(bl<<bB);++i) res+=a[i];
for(int i=bl+1;i<=br;++i) res+=s[i];
}
return res;
}
};
struct Query{
int l,r,id;
Query(){}
Query(int a,int b,int c){l=a;r=b;id=c;}
};
unsigned long long F[500005];
struct List{
int a[500005];
int s[500005];
bool b[500005];
int to[500005];
int top;
int stk[500005];
unsigned long long ans[2500005];
void clear(int n){for(int i=0;i<=n+1;++i)b[i]=to[i]=a[i]=s[i]=0;top=0;}
void geta(int* aa,int n){for(int i=1;i<=n;++i)a[i]=aa[i],s[i]=s[i-1]+a[i];}
void insert(int x){
// cerr<<"insert "<<x<<endl;
++top;
ans[top]=ans[top-1];
stk[top]=x;
b[x]=1;
if(!b[x-1]&&!b[x+1]){
to[x]=x;
return;
}
if(!b[x-1]){
ans[top]-=F[s[to[x+1]]-s[x]];
to[to[x]=to[x+1]]=x;
ans[top]+=F[s[to[x]]-s[x-1]];
}else if(!b[x+1]){
ans[top]-=F[s[x-1]-s[to[x-1]-1]];
to[to[x]=to[x-1]]=x;
ans[top]+=F[s[x]-s[to[x]-1]];
}else{
ans[top]+=(s[x-1]-s[to[x-1]-1])*(s[to[x+1]]-s[x]);
if(a[x]) ans[top]+=s[to[x+1]]-s[to[x-1]-1]-1;
int l=to[x-1],r=to[x+1];
to[l]=r;to[r]=l;
}
// cerr<<ans[top]<<endl;
}
void insert(int x){
// cerr<<"insert "<<x<<endl;
++top;
ans[top]=ans[top-1];
stk[top]=x;
b[x]=1;
if(!b[x-1]&&!b[x+1]){
to[x]=x;
return;
}
if(!b[x-1]){
ans[top]-=F[s[to[x+1]]-s[x]];
to[to[x]=to[x+1]]=x;
ans[top]+=F[s[to[x]]-s[x-1]];
}else if(!b[x+1]){
ans[top]-=F[s[x-1]-s[to[x-1]-1]];
to[to[x]=to[x-1]]=x;
ans[top]+=F[s[x]-s[to[x]-1]];
}else{
ans[top]-=F[s[x-1]-s[to[x-1]-1]];
ans[top]-=F[s[to[x+1]]-s[x]];
ans[top]+=F[s[to[x+1]]-s[to[x-1]-1]];
int l=to[x-1],r=to[x+1];
to[l]=r;to[r]=l;
}
// cerr<<ans[top]<<endl;
}
void undo(int cnt){
// cerr<<"undo "<<cnt<<endl;
while(cnt--){
int x=stk[top];
--top;
if(to[x-1]){
if(to[x-1]<x) to[to[x-1]]=x-1;
else to[x-1]=x-1;
}
if(to[x+1]){
if(to[x+1]>x) to[to[x+1]]=x+1;
else to[x+1]=x+1;
}
to[x]=b[x]=0;
}
}
void reset(){undo(top);}
unsigned long long ask(){return ans[top];}
};
struct FFT{
int n,Q,m,BB;
int a[500005];
Query q[500005];
unsigned long long ans[500005];
vector<int> oc[500005];
set<int> se;
vector<int> qr[500005];
int imp[500005];
int lb[500005];
List ls;
void clear(){se.clear();for(int i=1;i<=m;++i)oc[imp[i]].clear();for(int i=1;i*BB-BB+1<=n;++i)qr[i].clear();ls.clear(n);n=Q=0;}
void push_back(int x,int y){a[++n]=y;se.insert(x);oc[x].push_back(n);}
void add_query(Query qq){q[++Q]=qq;}
void run(){
// cerr<<"run\n";
ls.geta(a,n);
m=0;
for(int i=1;i<=n+1;++i) lb[i]=0;
for(auto x:se) imp[lb[x]=++m]=x;
BB=0.7*m/sqrt(Q);
if(BB==0) BB=1;
for(int i=n+1,lst=m+1;i;--i){
if(lb[i]) lst=lb[i];
else lb[i]=lst;
}
for(int i=1;i<=Q;++i){
q[i].l=lb[q[i].l];
q[i].r=lb[q[i].r+1]-1;
if(q[i].l<=q[i].r){
if((q[i].l-1)/BB==(q[i].r-1)/BB){
ls.reset();
for(int j=q[i].l;j<=q[i].r;++j)
for(auto p:oc[imp[j]]) ls.insert(p);
ans[q[i].id]+=ls.ask();
// cerr<<"ans="<<ans[i]<<endl;
}else qr[(q[i].l-1)/BB+1].push_back(i);
}
}
// cerr<<"--------\n";
for(int i=1;i*BB-BB+1<=n;++i){
if(qr[i].empty()) continue;
ls.reset();
int L=i*BB+1,l=i*BB+1,r=i*BB;
for(auto qi:qr[i]){
while(r<q[qi].r){
++r;
for(auto p:oc[imp[r]]) ls.insert(p);
}
int cnt=0;
while(l>q[qi].l){
--l;
for(auto p:oc[imp[l]]) ls.insert(p),++cnt;
}
ans[q[qi].id]+=ls.ask();
ls.undo(cnt);
l=L;
}
}
}
};
int n,Q;
int a[500005],p[500005];
int cnt[500005];
vector<int> oc[500005];
vector<int> vc[500005];
vector<int> qr[500005];
int mn[20][500005],mx[20][500005];
Query q[500005];
unsigned long long ans[500005];
NTT ntt1;
FFT fft1;
int askMn(int l,int r){
int len=__lg(r-l+1);
return min(mn[len][l],mn[len][r-(1<<len)+1]);
}
int askMx(int l,int r){
int len=__lg(r-l+1);
return max(mx[len][l],mx[len][r-(1<<len)+1]);
}
signed main(){
n=read();Q=read();
for(int i=1;i<=n;++i) F[i]=(unsigned long long)i*(i-1)/2;
for(int i=1;i<=n;++i) a[i]=read(),++cnt[a[i]],oc[a[i]].push_back(i);
for(int i=1;i<=n;++i) p[i]=read(),mn[0][i]=mx[0][i]=p[i];
for(int i=1;i<=Q;++i) q[i].id=i,q[i].l=read(),q[i].r=read();
sort(q+1,q+Q+1,[&](Query x,Query y){return x.r<y.r;});
for(int i=1;i<=Q;++i) qr[q[i].r].push_back(i);
for(int i=1;i<20;++i)
for(int j=1;j+(1<<i)-1<=n;++j){
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
}
for(int i=1;i<=n;++i){
// cerr<<"i="<<i<<endl;
sort(oc[i].begin(),oc[i].end());
if(cnt[i]<=B){
for(int j=0;j+1<cnt[i];++j){
for(int k=j+1;k<cnt[i];++k){
int l=askMn(oc[i][j],oc[i][k]);
int r=askMx(oc[i][j],oc[i][k]);
vc[r].push_back(l);
}
}
}else{
fft1.clear();
for(int j=0;j<cnt[i];++j){
fft1.push_back(p[oc[i][j]],1);
if(j+1!=cnt[i]){
if(oc[i][j]+1!=oc[i][j+1]){
int l=askMn(oc[i][j]+1,oc[i][j+1]-1);
int r=askMx(oc[i][j]+1,oc[i][j+1]-1);
fft1.push_back(l,0);
if(r!=l) fft1.push_back(r,0);
}
}
}
for(int j=1;j<=Q;++j) fft1.add_query(q[j]);
fft1.run();
}
}
for(int j=1;j<=Q;++j) ans[j]=fft1.ans[j];
for(int i=1;i<=n;++i){
for(int x:vc[i]) ntt1.add(x);
for(int qi:qr[i]) ans[q[qi].id]+=ntt1.ask(q[qi].l,i);
}
for(int i=1;i<=Q;++i) write(ans[i]);
return flush(),0;
}