#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[500005],lg[500005],ans[500005],n,m;
int b[20][500005],c[20][500005];
struct qry {
ll l,r,id;
} p[500005],p2[500005];
vector<int> col[500005];
vector<pair<int,int>> CC[500005];
const ll S=1000;
ll S2=0;
struct block {
const ll B=800;
int tag[805],z[500005];
void add(ll pos,ll v) {
z[pos]+=v;
tag[(pos-1)/B+1]+=v;
}
ll query(ll pos) {
ll v=(pos-1)/B+1,r=(n-1)/B+1,ans=0;
for (ll i=v+1; i<=r; i++)ans+=tag[i];
for (ll i=pos; i<=v*B; i++)ans+=z[i];
return ans;
}
} B;
inline ll getmx(ll l,ll r) {
ll k=lg[r-l+1];
return max(c[k][l],c[k][r-(1<<k)+1]);
}
inline ll getmi(ll l,ll r) {
ll k=lg[r-l+1];
return min(b[k][l],b[k][r-(1<<k)+1]);
}
int v[1000005],cnt[1000005],d[1000005],nxt[1000005],to[1000005],T;
vector<qry> Q[1000005];
struct CHAIN {
int vis[1000005],ano[1000005],top;
array<ll,3> stk[1000005];
ll gx;
inline void init(ll len) {
for (ll i=0; i<=len; i++)vis[i]=0,ano[i]=i;
top=0,gx=0;
}
inline void link(ll a) {
ll l=ano[a],r=ano[a+1];
gx+=(a-l+1)*(r-a);
ano[l]=r,ano[r]=l;
stk[++top]= {l,r,a};
// cout<<"?" <<a<<" "<< sz[a]<<" "<<sz[a+1]<<"\n";
}
inline void add(ll pos) {
vis[d[pos]]++;
if (vis[d[pos]]==2) {
link(d[pos]);
}
}
inline void del(ll pos) {
vis[d[pos]]--;
if (vis[d[pos]]==1) {
redo(d[pos]);
}
}
inline void redo(ll d) {
auto tp=stk[top--];
gx-=(tp[2]-tp[0]+1)*(tp[1]-tp[2]);
ano[tp[0]]=tp[2];
ano[tp[1]]=tp[2]+1;
}
} C;
#define fread fread_unlocked
#define fwrite fwrite_unlocked
const int LEN=1<<25;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');
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
n=read(),m=read();
for (ll i=1; i<=n; i++) {
a[i]=read();
col[a[i]].push_back(i);
}
for (ll i=1; i<=n; i++) {
if (i>1)lg[i]=lg[i>>1]+1;
b[0][i]=read();
c[0][i]=b[0][i];
}
for (ll i=1; i<=19; i++) {
for (ll j=1; j+(1ll<<i)-1<=n; j++) {
b[i][j]=min(b[i-1][j],b[i-1][j+(1ll<<(i-1))]);
c[i][j]=max(c[i-1][j],c[i-1][j+(1ll<<(i-1))]);
}
}
for (ll i=1; i<=m; i++) {
read(p[i].l),read(p[i].r);
p[i].id=i;
}
for (ll i=1; i<=n; i++) {
if (col[i].size()<=S) {
for (ll j=0; j+1<(ll)col[i].size(); j++) {
CC[getmx(col[i][j],col[i][j+1])].push_back({i,j});
// for (ll k=j+1; k<(ll)col[i].size(); k++) {
// ll mi=getmi(col[i][j],col[i][k]),mx=getmx(col[i][j],col[i][k]);
//// CC[.emplace_back(mi);
// ++TT;
// V[TT]=mi;
// nxt1[TT]=head[mx];
// head[mx]=TT;
//
// }
}
}
}
sort(p+1,p+1+m,[](qry a,qry b) {
return a.r<b.r;
});
ll ps=0;
for (ll i=1; i<=m; i++) {
while (ps+1<=n&&ps+1<=p[i].r) {
for (pair<ll,ll> j:CC[ps+1]) {
ll mi=getmi(col[j.first][j.second],col[j.first][j.second+1]),mx=ps+1;
for (ll k=j.second; k>=0; k--) {
ll pmi=mi,pmx=mx;
for (ll l=j.second+1; l+1<=col[j.first].size(); l++) {
if (l==j.second+1){
}else{
ll tmx=getmx(col[j.first][l-1],col[j.first][l]),tmi=getmi(col[j.first][l-1],col[j.first][l]);
if (tmx>=pmx)break;
pmx=max(pmx,tmx);
pmi=min(pmi,tmi);
}
if (pmx!=ps+1)break;
B.add(pmi,1);
}
if (k!=0) {
mx=max(mx,getmx(col[j.first][k-1],col[j.first][k]));
mi=min(mi,getmi(col[j.first][k-1],col[j.first][k]));
}
if (mx!=ps+1)break;
}
}
ps++;
}
ans[p[i].id]+=B.query(p[i].l);
}
for (ll i=1; i<=n; i++) {
if (col[i].size()>S) {
T=i;
ll N=col[i].size();
vector<ll> book;
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
book.push_back(mi);
book.push_back(mx);
}
sort(book.begin(),book.end());
book.erase(unique(book.begin(),book.end()),book.end());
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
++cnt[lower_bound(book.begin(),book.end(),mi)-book.begin()+1];
++cnt[lower_bound(book.begin(),book.end(),mx)-book.begin()+1];
}
for (ll j=1; j<=(ll)book.size(); j++)cnt[j]+=cnt[j-1];
ll lim=cnt[book.size()];
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
ll mip=lower_bound(book.begin(),book.end(),mi)-book.begin()+1;
ll mxp=lower_bound(book.begin(),book.end(),mx)-book.begin()+1;
d[cnt[mip]--]=j;
to[cnt[mip]+1]=mi;
d[cnt[mxp]--]=j;
to[cnt[mxp]+1]=mx;
}
ll ps=0;
for (ll j=1; j<=n; j++) {
while (ps+1<=lim&&to[ps+1]<=j)ps++;
nxt[j]=ps;
}
S2=0.7*lim/sqrt(m)+1;
for (ll j=1; j<=m; j++) {
p2[j].l=nxt[p[j].l-1]+1,p2[j].r=nxt[p[j].r],p2[j].id=p[j].id;
if (p2[j].l<=p2[j].r) {
if ((p2[j].l-1)/S2==(p2[j].r-1)/S2) {
C.init(N);
for (ll k=p2[j].l; k<=p2[j].r; k++) {
C.add(k);
}
ans[p2[j].id]+=C.gx;
} else {
Q[(p2[j].l-1)/S2+1].push_back(p2[j]);
}
}
}
for (ll j=1; j<=(lim-1)/S2+1; j++) {
if (!Q[j].size())continue;
ll lb=j*S2;
C.init(N);
ll L=lb+1,R=lb;
// cout<<(j-1)*S2+1<<"~"<<j*S2<<":\n";
for (qry k:Q[j]) {
// cout<<k.l<<","<<k.r<<"\n";
while (R<k.r)C.add(++R);
while (L>k.l)C.add(--L);
ans[k.id]+=C.gx;
while (L<lb+1)C.del(L++);
}
}
for (ll j=0; j<=lim; j++)cnt[j]=to[j]=nxt[j]=d[j]=0,Q[j].clear();
}
}
for (ll i=1; i<=m; i++) {
write(ans[i]);
}
return 0;
}
/*
■■■■■ ■■ ■■■ ■■■ ■ ■ ■ ■■■■ ■■■■
■ ■■ ■■ ■ ■■ ■ ■■ ■ ■ ■■ ■ ■■ ■■ ■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■■ ■■ ■■ ■ ■■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■ ■ ■■ ■■
■ ■ ■■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■■ ■ ■■■ ■ ■■■ ■■ ■■ ■■ ■■■
■■■■■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■ ■ ■■
■ ■■ ■■ ■■ ■■ ■■ ■■ ■■ ■ ■■ ■■
■ ■■ ■■■■ ■■■■ ■■ ■■ ■■■■■■ ■■■■
*/