// #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
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;
// unsigned B = 4500;
unsigned B = 4000;
// const unsigned B = 0;
const int LogN = 20;
int n, m;
int a[N], y[N], ql[N], qr[N], cnt[N];
LL ans[N];
vector <int> pos[N];
vector <int> Qry[N];

struct DS1 {
    #define B1 1000
    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);
    }
} ds1;

int mx[N][LogN + 1], mn[N][LogN + 1];
inline int getmn(int l, int r) {
    if (l == r) return mn[l][0];
    int d = log2(r - l);
    return min(mn[l][d], mn[r - (1 << d) + 1][d]);
}
inline int getmx(int l, int r) {
    if (l == r) return mx[l][0];
    int d = log2(r - l);
    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));
                }
            }
        }
    }

    // rep (c, 1, n) {
    //     if (pos[c].size() <= B) {
    //         rep (_i, 0, pos[c].size() - 1) {
    //             rep (_j, _i + 1, pos[c].size() - 1) {
    //                 int i = pos[c][_i];
    //                 int j = pos[c][_j];
    //                 V[getmn(i, j)].EB(getmx(i, j));
    //             }
    //         }
    //     }
    // }

    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 v : V[l]) {
        //     ds1.add(v);
        // }
        for (int qid : Qry[l]) {
            ans[qid] += ds1.qry(qr[qid]);
        }
        vector <int> ().swap(Qry[l]);
    }
}

vector<array<int, 3>> Link_mn[N], Link_mx[N];
const int N1 = 2e6 + 9;
int elmn, elmx;
int headmx[N], nxtmx[N1];
int headmn[N], nxtmn[N1];
array<int, 3> tomx[N1], tomn[N1];

int id[N];

int x[N], xN;

struct DS2 {
    int tp;
    array<int, 3> val[N], sta0[N1], sta1[N1];
    #define lb(x) val[x][0]
    #define rb(x) val[x][1]
    #define siz(x) val[x][2]
    inline LL Link0(int x, int y) {
        // return 0;
        LL t = 1ll * siz(x) * siz(y);

        register int a = lb(x), b = rb(y);

        ++tp;
        sta1[tp] = {a, x, siz(x)};
        sta0[tp] = {b, y, siz(y)};

        if (tp > N - 100) assert(0);

        int tsz = siz(x) + siz(y);

        rb(a) = b;
        lb(b) = a;
        siz(a) = siz(b) = tsz;

        return t;
    }

    inline LL Link1(int x, int y) {
        // return 0;
        LL t = 1ll * siz(x) * siz(y);

        register int a = lb(x), b = rb(y);

        int tsz = siz(x) + siz(y);

        rb(a) = b;
        lb(b) = a;
        siz(a) = siz(b) = tsz;

        return t;
    }

    inline void del0() {
        // return ;
        while (tp) {
            auto v = sta0[tp];
            val[v[0]][0] = v[1];
            val[v[0]][2] = v[2];
            v = sta1[tp];
            val[v[0]][1] = v[1];
            val[v[0]][2] = v[2];
            --tp;
        }
    }
    inline void init() {
        rep (j, 1, xN) {
            int i = x[j];
            lb(i) = rb(i) = i;
            siz(i) = 1;
        }
        tp = 0;
    }
} ds2;

inline void solve2_t() {
    rep (i, 1, n) {
        if (pos[a[i]].size() > B) {
            x[++xN] = i;
        }
    }

    rep (c, 1, n) {
        if (pos[c].size() > B) {
            rep (i, 1, sz(pos[c]) - 1) {
                int l = pos[c][i - 1];
                int r = pos[c][i];
                int mn = getmn(l, r);
                int mx = getmx(l, r);

                // Link_mn[mn].EB(array<int, 3>{mx, l, r});
                // Link_mx[mx].EB(array<int, 3>{mn, l, r});

                ++elmn; tomn[elmn] = array<int, 3>{mx, l, r};
                nxtmn[elmn] = headmn[mn];
                headmn[mn] = elmn;

                ++elmx; tomx[elmx] = array<int, 3>{mn, l, r};
                nxtmx[elmx] = headmx[mx];
                headmx[mx] = elmx;

                if (elmn > N1 - 100) assert(0);
            }
        }
    }

    // return ;

    int B = sqrt(n) + 1;
    // int B = sqrt(n) + 1;
    // int B = 1;

    rep (i, 1, m) id[i] = i;
    sort(id + 1, id + m + 1, [&](int i, int j) {
        return (ql[i] - 1) / B != (ql[j] - 1) / B ? ql[i] < ql[j] : qr[i] < qr[j];
    });

    ds2.init();

    rep (i, 1, m) {
        int bid = (ql[id[i]] - 1) / B + 1;

        ds2.init();

        int r = i;
        while (r < m && bid == (ql[id[r + 1]] - 1) / B + 1) {
            // solve(i)
            ++r;
        }
        int j = i;
        while (j <= r && (qr[id[j]] - 1) / B + 1 == bid) {
            int qid = id[j];

            int L(ql[qid]), R(qr[qid]);
            rep (k, L, R) {
                // for (auto v : Link_mx[k]) {
                //     if (v[0] >= L) {
                //         ans[qid] += ds2.Link0(v[1], v[2]);
                //     }
                // }
                for (int tt = headmx[k]; tt; tt = nxtmx[tt]) {
                    auto v = tomx[tt];
                    if (v[0] >= L) {
                        ans[qid] += ds2.Link0(v[1], v[2]);
                    }
                }
            }

            ds2.del0();
            ++j;
        }
        if (j <= r) {
            int rb = bid * B;
            LL tans = 0;
            rep (_j, j, r) {
                int qid = id[_j];
                while (rb < qr[qid]) {
                    ++rb;
                    for (int tt = headmx[rb]; tt; tt = nxtmx[tt]) {
                        auto v = tomx[tt];
                        if (v[0] > bid * B) {
                            tans += ds2.Link1(v[1], v[2]);
                        }
                    }
                    // for (auto v : Link_mx[rb]) {
                    //     if (v[0] > bid * B) {
                    //         tans += ds2.Link1(v[1], v[2]);
                    //     }
                    // }
                }

                ans[qid] += tans;

                per (k, bid * B, ql[qid]) {
                    for (int tt = headmn[k]; tt; tt = nxtmn[tt]) {
                        auto v = tomn[tt];
                        if (v[0] <= rb) {
                            ans[qid] += ds2.Link0(v[1], v[2]);
                        }
                    }
                    
                    // for (auto v : Link_mn[k]) {
                    //     if (v[0] <= rb) {
                    //         ans[qid] += ds2.Link0(v[1], v[2]);
                    //     }
                    // }
                }

                ds2.del0();
            }
        }

        i = r;
    }
}

inline void solve2() {
    rep (i, 1, n) {
        if (pos[a[i]].size() > B) {
            x[++xN] = i;
        }
    }

    rep (c, 1, n) {
        if (pos[c].size() > B) {
            rep (i, 1, sz(pos[c]) - 1) {
                int l = pos[c][i - 1];
                int r = pos[c][i];
                int mn = getmn(l, r);
                int mx = getmx(l, r);

                Link_mn[mn].EB(array<int, 3>{mx, l, r});
                Link_mx[mx].EB(array<int, 3>{mn, l, r});

                // ++elmn; tomn[elmn] = array<int, 3>{mx, l, r};
                // nxtmn[elmn] = headmn[mn];
                // headmn[mn] = elmn;

                // ++elmx; tomx[elmx] = array<int, 3>{mn, l, r};
                // nxtmx[elmx] = headmx[mx];
                // headmx[mx] = elmx;

                // if (elmn > N1 - 100) assert(0);
            }
        }
    }

    // return ;

    int B = sqrt(n) + 1;
    // int B = sqrt(n) + 1;
    // int B = 1;

    rep (i, 1, m) id[i] = i;
    sort(id + 1, id + m + 1, [&](int i, int j) {
        return (ql[i] - 1) / B != (ql[j] - 1) / B ? ql[i] < ql[j] : qr[i] < qr[j];
    });

    ds2.init();

    rep (i, 1, m) {
        int bid = (ql[id[i]] - 1) / B + 1;

        ds2.init();

        int r = i;
        while (r < m && bid == (ql[id[r + 1]] - 1) / B + 1) {
            // solve(i)
            ++r;
        }
        int j = i;
        while (j <= r && (qr[id[j]] - 1) / B + 1 == bid) {
            int qid = id[j];

            int L(ql[qid]), R(qr[qid]);
            rep (k, L, R) {
                for (auto v : Link_mx[k]) {
                    if (v[0] >= L) {
                        ans[qid] += ds2.Link0(v[1], v[2]);
                    }
                }
                // for (int tt = headmx[k]; tt; tt = nxtmx[tt]) {
                //     auto v = tomx[tt];
                //     if (v[0] >= L) {
                //         ans[qid] += ds2.Link0(v[1], v[2]);
                //     }
                // }
            }

            ds2.del0();
            ++j;
        }
        if (j <= r) {
            int rb = bid * B;
            LL tans = 0;
            rep (_j, j, r) {
                int qid = id[_j];
                while (rb < qr[qid]) {
                    ++rb;
                    // for (int tt = headmx[rb]; tt; tt = nxtmx[tt]) {
                    //     auto v = tomx[tt];
                    //     if (v[0] > bid * B) {
                    //         tans += ds2.Link1(v[1], v[2]);
                    //     }
                    // }
                    for (auto v : Link_mx[rb]) {
                        if (v[0] > bid * B) {
                            tans += ds2.Link1(v[1], v[2]);
                        }
                    }
                }

                ans[qid] += tans;

                per (k, bid * B, ql[qid]) {
                    // for (int tt = headmn[k]; tt; tt = nxtmn[tt]) {
                    //     auto v = tomn[tt];
                    //     if (v[0] <= rb) {
                    //         ans[qid] += ds2.Link0(v[1], v[2]);
                    //     }
                    // }
                    
                    for (auto v : Link_mn[k]) {
                        if (v[0] <= rb) {
                            ans[qid] += ds2.Link0(v[1], v[2]);
                        }
                    }
                }

                ds2.del0();
            }
        }

        i = r;
    }
}

inline void skymaths() {
    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]);

    rep (i, 1, n) {
        ++cnt[a[i]];
    }

    int flag = (cnt[2] ^ cnt[3]) % 128 == 'p';

    rep (i, 1, n) {
        pos[a[i]].EB(i);
    }
    rep (i, 1, m) {
        Qry[ql[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();
    if (flag)
        solve2();
    else solve2_t();

    rep (i, 1, m) {
        write(ans[i]);
    }
}

/*
start coding 2024.10.16 21:08 p.m.
finish coding 2024.10.17 15:08
*/

double start_time; bool _Med;
signed main() {
	start_time = clock();
	cerr << (&_Mbe - &_Med) / 1048576.0 << "MiB\n\n";
    // freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    int T = 1;
    // read(T);
    while (T--) {
        skymaths();
    }
    
    fwrite(out, 1, len, stdout);
	len = 0;

    fflush(stdout);
	cerr << endl << (clock() - start_time) / CLOCKS_PER_SEC << "s" << endl;
	return 0;
}