#include <iostream>
#include <algorithm>
#include <string.h>
#include <cassert>
#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 <= n; j++) (o[j] ? (_o[++ocnt] = j) : 0), o[j] += o[j - 1];
            for (int j = 1; j <= q; j++) {
                // assert(o[qrec[j].l] + (o[qrec[j].l] == o[qrec[j].l - 1]) == lower_bound(key + 1, key + kcnt + 1, qrec[j].l) - key);
                // assert(o[qrec[j].r] == upper_bound(key + 1, key + kcnt + 1, qrec[j].r) - key - 1);
                // qs[j].l = lower_bound(key + 1, key + kcnt + 1, qrec[j].l) - key;
                qs[j].l = o[_p[qrec[j].l]] + (o[_p[qrec[j].l]] == o[_p[qrec[j].l] - 1]);
                // qs[j].r = upper_bound(key + 1, key + kcnt + 1, qrec[j].r) - key - 1;
                qs[j].r = o[_p[qrec[j].r]];
                qs[j].id = j;
            }
            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;
}