#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
static char buf[1000005], *p1 = buf, *p2 = buf;
inline char nnc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000005, stdin), p1 == p2) ? EOF : *p1++; }
// #define nnc getchar
inline int read() {
int ret = 0, neg = 0;
char c = 0;
while (c < '0' || c > '9') c = nnc(), c == '-' ? (neg = 1) : 0;
while ('0' <= c && c <= '9') ret = ret * 10 + c - 48, c = nnc();
return ret * (neg ? -1 : 1);
}
int n, q, B;
int a[500005], p[500005], _p[500005];
struct qquery {
int l, r, id;
} qs[500005], qrec[500005];
int cnt[500005], big[500005], lg2[500005];
long long ans[500005];
vector<int> vec[500005];
struct RMQ {
pair<int, int> mx[21][500005], mn[21][500005];
void Build() {
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
}
}
}
inline pair<int, int> QueryMax(int l, int r) {
if (l > r)
return make_pair(0, 0);
int k = lg2[r - l + 1];
return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}
inline pair<int, int> QueryMin(int l, int r) {
if (l > r)
return make_pair(n + 1, 0);
int k = lg2[r - l + 1];
return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}
inline int Qmax(int l, int r) { return QueryMax(l, r).first; }
inline int Qmin(int l, int r) { return QueryMin(l, r).first; }
} rmq;
struct Block {
int bel[500005], S;
int s[1005], val[500005];
int L[1005], R[1005];
void Build(int x) {
S = x;
for (int i = 1; i <= n;) {
int id = (i - 1) / S + 1;
L[id] = i, R[id] = min(n, i + S - 1);
for (int j = L[id]; j <= R[id]; j++) bel[j] = id;
i += S;
}
}
inline void Add(int x, int y = 1) { val[x] += y, s[bel[x]] += y; }
int Query(int l, int r) {
int ret = 0;
if (bel[l] == bel[r]) {
for (int i = l; i <= r; i++) ret += val[i];
return ret;
}
int pl = bel[l], pr = bel[r];
for (int i = l; i <= R[pl]; i++) ret += val[i];
for (int i = pl + 1; i < pr; i++) ret += s[i];
for (int i = L[pr]; i <= r; i++) ret += val[i];
return ret;
}
} blk;
namespace Small {
struct Cpr {
int v, L, l, r, R, id;
} cpr[500005];
int cprcnt;
inline void decpr(Cpr c) {
int x = c.id;
for (int i = c.L; i <= c.l; i++) {
for (int j = c.r; j <= c.R; j++)
blk.Add(rmq.Qmax(vec[x][i], vec[x][j]));
}
}
void work() {
blk.Build(1000);
for (int i = 1; i <= n; i++) {
if (big[i])
continue;
for (int j = 1; j < cnt[i]; j++) {
int a = vec[i][j - 1], b = vec[i][j];
int x = j - 1, y = j, z = rmq.Qmin(a, b);
while (x && rmq.Qmin(vec[i][x - 1], b) == z) --x;
if (rmq.QueryMin(a, b).second != b)
while (y < cnt[i] - 1 && rmq.Qmin(a, vec[i][y + 1]) == z) ++y;
cpr[++cprcnt] = (Cpr) { z, x, j - 1, j, y, i };
}
}
sort(cpr + 1, cpr + cprcnt + 1, [](Cpr a, Cpr b) { return a.v < b.v; });
sort(qs + 1, qs + q + 1, [](qquery a, qquery b) { return a.l < b.l; });
for (int i = q, j = cprcnt; i; i--) {
while (j && cpr[j].v >= qs[i].l) decpr(cpr[j--]);
ans[qs[i].id] += blk.Query(1, qs[i].r);
}
}
}
namespace Large {
int onv[500005], o[500005], _o[500005], ocnt;
int key[500005], kcnt, S, T;
int bel[500005];
struct List {
int al[500005], ar[500005], av[500005];
pair<int, int> his[500005];
int n, cur;
long long ans;
bool act[500005];
void ini(int x) {
ans = cur = 0;
n = x;
for (int i = 1; i <= x; i++) al[i] = ar[i] = i, av[i] = (onv[p[_o[i]]] == 1), act[i] = 0;
}
void Connect(int x, int y) {
++cur;
his[cur] = make_pair(x, y);
int l = al[x], r = ar[y];
ans += 1ll * av[l] * av[y];
ar[l] = r, al[r] = l, av[l] += av[y];
}
void Rollback(int t) {
while (cur > t) {
int x = his[cur].first, y = his[cur].second;
int l = al[x], r = ar[y];
ar[l] = x, al[r] = y, av[l] -= av[y];
ans -= 1ll * av[l] * av[y];
--cur;
}
}
void Insert(int i) {
act[i] = 1;
(act[i - 1]) ? Connect(i - 1, i) : void();
(act[i + 1]) ? Connect(i, i + 1) : void();
}
} lis;
int R[500005];
vector<qquery> v1[500005];
vector<pair<int, int> > v2[500005];
void Backroll_MoQueue() {
S = 1 + kcnt / sqrt(q);
for (int i = 1; i <= kcnt; i++) bel[i] = (i - 1) / S + 1, R[bel[i]] = i;
T = bel[kcnt];
for (int i = 1; i <= T; i++) v1[i].clear();
// sort(qs + 1, qs + q + 1, [](qquery a, qquery b) { return bel[a.l] == bel[b.l] ? (a.r < b.r) : (a.l < b.l); });
for (int i = 1; i <= q; i++) qs[i].l <= qs[i].r ? v1[bel[qs[i].l]].emplace_back(qs[i]) : void();
lis.ini(kcnt);
for (int id = 1; id <= T; id++) {
lis.Rollback(0);
int mxr = 0;
for (auto v : v1[id]) v2[v.r].emplace_back(make_pair(v.l, v.id)), mxr = max(mxr, v.r);
for (int rr = R[id - 1] + 1; rr <= R[id]; rr++) {
for (auto v : v2[rr]) {
for (int a = v.first; a <= rr; a++) lis.Insert(o[_p[key[a]]]);
ans[v.second] += lis.ans;
lis.Rollback(0);
for (int a = v.first; a <= rr; a++) lis.act[o[_p[key[a]]]] = 0;
}
v2[rr].clear();
}
for (int r = R[id] + 1; r <= mxr; r++) {
lis.Insert(o[_p[key[r]]]);
for (auto v : v2[r]) {
int l = R[id] + 1;
int tmp = lis.cur;
while (l > v.first) lis.Insert(o[_p[key[--l]]]);
ans[v.second] += lis.ans;
lis.Rollback(tmp);
while (l <= R[id]) lis.act[o[_p[key[l++]]]] = 0;
}
v2[r].clear();
}
while (mxr > R[id]) lis.act[o[_p[key[mxr--]]]] = 0;
}
}
void work() {
for (int i = 1; i <= n; i++) {
if (!big[i])
continue;
for (int j = 0; j <= n + 1; j++) onv[j] = 0, o[j] = 0;
ocnt = kcnt = 0;
for (int j = 1; j < cnt[i]; j++) {
int a = vec[i][j - 1], b = vec[i][j];
onv[rmq.Qmax(a, b)] = onv[rmq.Qmin(a, b)] = 2;
}
for (int j = 0; j < cnt[i]; j++) onv[p[vec[i][j]]] = 1;
for (int j = 1; j <= n; j++) onv[j] ? (key[++kcnt] = j, o[_p[j]] = 1) : 0;
for (int j = 1; j <= q; j++) {
qs[j].l = lower_bound(key + 1, key + kcnt + 1, qrec[j].l) - key;
qs[j].r = upper_bound(key + 1, key + kcnt + 1, qrec[j].r) - key - 1;
qs[j].id = j;
}
for (int j = 1; j <= n; j++) (o[j] ? (_o[++ocnt] = j) : 0), o[j] += o[j - 1];
Backroll_MoQueue();
}
}
}
int main() {
// freopen("G.in", "r", stdin);
// freopen("G.out", "w", stdout);
B = 3200;
n = read(), q = read();
lg2[0] = -1;
for (int i = 1; i <= n; i++) lg2[i] = lg2[i - 1] + ((i & (i - 1)) == 0);
for (int i = 1; i <= n; i++) a[i] = read(), cnt[a[i]]++, vec[a[i]].emplace_back(i);
for (int i = 1; i <= n; i++) p[i] = read(), rmq.mx[0][i] = rmq.mn[0][i] = make_pair(p[i], i), _p[p[i]] = i;
for (int i = 1; i <= q; i++) qs[i].l = read(), qs[i].r = read(), qs[i].id = i;
for (int i = 1; i <= n; i++) big[i] = (cnt[i] >= B);
memcpy(qrec, qs, sizeof qs);
rmq.Build();
Small::work();
Large::work();
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
return 0;
}