// #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 = 3000;
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], ord, qrys[N];

LL ans[N];

struct DS1 {
    #define B1 800
    int sum1[N], sum2[N];
    // sum1 是整体，sum2 是部分
    void add(int x) {
        ++sum1[(x - 1) / B1 + 1];
        ++sum2[x];
    }
    int qry(int x) {
        int v = 0;
        rep (id, 1, (x - 1) / B1) v += sum1[id];
        rep (i, (x - 1) / B1 * B1 + 1, x) v += sum2[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]);
}

struct node1 {
    int c, L, l, r, R;
    node1() {}
    node1(int c, int L, int l, int r, int R):c(c), L(L), l(l), r(r), R(R) {} 
} ;
vector <node1> V[N];

inline void solve1() {
    #define sz(V) (int)(V.size())

    rep (c, 1, n) {
        if (pos[c].size() <= B && pos[c].size() > 1) {
            int l, r, L, R, mn;
            l = 0, r = 1;
            mn = getmn(pos[c][l], pos[c][r]);
            L = l; while (L > 0 && getmn(pos[c][L - 1], pos[c][r]) == mn) --L;
            R = r; while (R < sz(pos[c]) - 1 && getmn(pos[c][l], pos[c][R + 1]) == mn) ++R;
            V[mn].EB(node1(c, L, l, r, R));
            rep (i, 2, pos[c].size() - 1) {
                l = i - 1, r = i;
                int t = getmn(pos[c][l], pos[c][r]);
                if (mn == t) {
                    // 如果和上一个共用（注意是 min 相同而非 min 为最左边的）
                    V[mn].EB(node1(c, l, l, r, R));
                }
                else {
                    mn = t;
                    L = l; while (L > 0 && getmn(pos[c][L - 1], pos[c][r]) == mn) --L;
                    R = r; while (R < sz(pos[c]) - 1 && getmn(pos[c][l], pos[c][R + 1]) == mn) ++R;
                    V[mn].EB(node1(c, L, l, r, R));
                }
            }
        }
    }

    per (l, n, 1) {
        for (node1 v : V[l]) {
            rep (i, v.L, v.l) {
                rep (j, v.r, v.R) {
                    ds1.add(getmx(pos[v.c][i], pos[v.c][j]));
                }
            }
        }
        vector <node1> ().swap(V[l]);
        for (int qid : Qry[l]) {
            ans[qid] = ds1.qry(qr[qid]);
        }
        vector <int> ().swap(Qry[l]);
    }

    #undef sz
}

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) {
    int s = pos[c].size();
    rep (i, 1, s - 1) {
        op[i] = {getmn(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];
    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[N] && 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]);
    }
    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};
}

signed main() {
    // file("a");
    // freopen("a.in", "r", stdin);

    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(qr[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;
}