// #pragma GCC optimize("-Ofast", "-finline", "-funroll-loops", "-fno-stack-protector")
#include<bits/stdc++.h>
#define rep(i,l,r) for (int i(l), i##end(r); i <= i##end; ++i)
#define per(i,r,l) for (int i(r), i##end(l); i >= i##end; --i)
#define LL long long
#define PII pair <int, int>
#define fi first
#define se second
#define EB emplace_back
// #define file(s) freopen(#s".in", "r", stdin), freopen(#s".out", "w", stdout)
using namespace std;
bool _Mbe;
char ibuf[1 << 25], *iS, *iT;
// #define getc() (((iS == iT) && (iT = ((iS = ibuf) + fread(ibuf, 1, 1 << 20)))), (iS == iT) ? EOF : *(iS++))
#define getc() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, 1 << 25, stdin), (iS == iT ? EOF : *iS++) : *iS++)
char out[1 << 25]; int len;
template <typename T>
inline void read(T &x) {
x = 0; bool f = 0; char ch = getc();
while (ch < '0' || ch > '9') f ^= ch == '-', ch = getc();
while (ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getc();
if (f) x = -x;
}
template <typename Tx, typename ...Ty>
inline void read(Tx &x, Ty &...y) {
read(x);
read(y...);
}
template <typename T>
inline void Write(T x) {
if (x > 9) Write(x / 10);
out[len++] = x % 10 + '0';
}
template <typename T>
inline void write(T x, char ch = '\n') {
Write(x);
out[len++] = ch;
}
template <typename T> inline void cmin(T &x, T y) { if (x > y) x = y;}
template <typename T> inline void cmax(T &x, T y) { if (x < y) x = y;}
/* - - - all above template - - - */
const int N = 5e5 + 9;
const int LogN = 19;
const unsigned B = 1000;
// const unsigned B = 0;
int n, m;
int a[N], y[N], ql[N], qr[N];
int mx[N][LogN + 1], mn[N][LogN + 1];
vector <int> pos[N], Qry[N], qrys[N], ord;
LL ans[N];
struct DS1 {
int sum1[N], sum2[N], sum3[N];
// sum1 是整体，sum2 是部分
void add(int x) {
++sum1[x], ++sum2[x >> 7], ++sum3[x >> 14];
}
int qry(int x) {
if (!x) return 0;
int v = 0;
for (int i = ((x >> 7) << 7); i <= x; ++i) v += sum1[i];
for (int i = ((x >> 14) << 7); i < (x >> 7); ++i) v += sum2[i];
for (int i = 0; i < (x >> 14); ++i) v += sum3[i];
return v;
}
int qry(int l, int r) {
return qry(r) - qry(l - 1);
}
#undef B1
} ds1;
inline int getmn(int l, int r) {
int d = log2(r - l + 1);
return min(mn[l][d], mn[r - (1 << d) + 1][d]);
}
inline int getmx(int l, int r) {
int d = log2(r - l + 1);
return max(mx[l][d], mx[r - (1 << d) + 1][d]);
}
vector <PII> cur[N];
vector <int> las[N];
int rk[N];
inline void solve1() {
rep (i, 1, n) if (pos[i].size() <= B) {
int s = pos[i].size();
for (int x = 0; x < s; ++x) rk[pos[i][x]] = x;
for (int x = 0; x < s - 1; ++x) {
int mn = getmn(pos[i][x], pos[i][x + 1]);
int mx = getmx(pos[i][x], pos[i][x + 1]);
cur[i].EB(mn, mx);
las[mn].EB(pos[i][x]);
}
}
per (i, n, 1) {
for (int o : las[i]) {
int c = a[o], x = rk[o], s = pos[c].size();
vector <PII> &sg = cur[c];
for (int l = x, mx = sg[x].se; l >= 0; --l) {
if (l < x && sg[l].fi <= i) break;
mx = max(mx, sg[l].se);
int vr = mx;
rep (r, x + 1, s - 1) {
if (sg[r - 1].fi < i) break;
vr = max(vr, sg[r - 1].se);
ds1.add(vr);
}
}
}
for (int o : Qry[i]) {
// cerr << "qry in\n";
ans[o] += ds1.qry(qr[o]);
}
}
}
array<int, 2> op[N], ml[N], mr[N];
int w[N], wl[N], wr[N], tl[N], tr[N], tid[N], lb[N], rb[N], vl[N], sta[N];
inline void solve2(int c) {
// cerr << "input " << c << endl;
int s = pos[c].size();
rep (i, 1, s - 1) {
// op[e] ：e 贡献的限制
op[i] = {getmn(pos[c][i - 1], pos[c][i]), getmx(pos[c][i - 1], pos[c][i])};
w[op[i][0]] = w[op[i][1]] = 1;
}
int iN = 0;
rep (i, 1, n) if (w[i]) vl[++iN] = i, wl[i] = wr[i] = iN;
rep (i, 1, n) if (!wl[i]) wl[i] = wl[i - 1];
per (i, n, 1) if (!wr[i]) wr[i] = wr[i + 1];
// printf("wl = "); rep (i, 1, n) printf("%d%c", wl[i], " \n"[i == n]);
// printf("wr = "); rep (i, 1, n) printf("%d%c", wr[i], " \n"[i == n]);
// printf("vl = "); rep (i, 1, n) printf("%d%c", vl[i], " \n"[i == n]);
rep (i, 1, s - 1) {
int l = op[i][0] = wl[op[i][0]], r = op[i][1] = wr[op[i][1]];
ml[l][ml[l][0] > 0] = mr[r][mr[r][0] > 0] = i;
}
int tN = 0;
for (int i : ord) {
if (ql[i] <= vl[iN] && vl[1] <= qr[i] && wr[ql[i]] <= wl[qr[i]]) {
++tN;
tl[tN] = wr[ql[i]], tr[tN] = wl[qr[i]];
tid[tN] = i;
}
}
if (!tN) return ;
int B2 = iN / sqrt(tN) + 1;
rep (i, 1, tN) qrys[(tl[i] - 1) / B2 + 1].EB(i);
rep (b, 1, (tN - 1) / B2 + 1) if (qrys[b].size()) {
int o = min(b * B2, tN), nowR = o + 1;
rep (i, 1, s) lb[i] = rb[i] = i;
LL sum = 0;
auto link = [&](int e) {
sum += 1ll * (e - lb[e] + 1) * (rb[e + 1] - (e + 1) + 1);
rb[lb[e]] = rb[e + 1];
lb[rb[e + 1]] = lb[e];
} ;
for (auto q : qrys[b]) {
if (tr[q] <= o) {
int tp = 0;
rep (i, tl[q], tr[q]) {
for (int e : ml[i]) if (e && op[e][1] <= tr[q]) {
link(e), sta[++tp] = e;
}
}
ans[tid[q]] += sum, sum = 0;
per (i, tp, 1) {
int x = sta[i];
rb[lb[x]] = x;
lb[rb[x + 1]] = x + 1;
}
continue;
}
for (; nowR <= tr[q]; ++nowR) for (int e : mr[nowR]) if (op[e][0] > o) link(e);
int tp = 0;
LL rem = sum;
per (i, o, tl[q]) for (int e : ml[i]) if (e && op[e][1] < nowR) {
link(e), sta[++tp] = e;
}
ans[tid[q]] += sum, sum = rem;
per (i, tp, 1) {
int x = sta[i];
rb[lb[x]] = x;
lb[rb[x + 1]] = x + 1;
}
}
// vector <int> ().swap(qrys[b]);
qrys[b].clear;
}
memset(w, 0, sizeof(w));
memset(wl, 0, sizeof(wl));
memset(wr, 0, sizeof(wr));
rep (i, 1, tN) ml[i] = mr[i] = {0, 0};
}
/*
code from DaiRuiChen007
*/
signed main() {
ios::sync_with_stdio(false);
read(n, m);
rep (i, 1, n) read(a[i]);
rep (i, 1, n) read(y[i]);
rep (i, 1, m) read(ql[i], qr[i]), ord.EB(i), Qry[ql[i]].EB(i);
sort(ord.begin(), ord.end(), [](int x, int y) { return qr[x] < qr[y]; }) ;
rep (i, 1, n) pos[a[i]].EB(i);
rep (i, 1, n) mx[i][0] = mn[i][0] = y[i];
rep (j, 1, LogN) {
rep (i, 1, n - (1 << j) + 1) {
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
}
}
solve1();
rep (c, 1, n) {
if (pos[c].size() > B) {
solve2(c);
}
}
rep (i, 1, m) write(ans[i]);
fwrite(out, 1, len, stdout);
fflush(stdout);
return 0;
}