#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

// #include "../cpp-dump/cpp-dump.hpp"  
#define cpp_dump(...) void()
using ll = long long;

template <int B>
struct array {
  std::vector<int> a, b;
  array(int n) : a(n), b((n - 1) / B + 1) {}
  void add(int x) { a[x] += 1, b[x / B] += 1; }
  int query(int x) {
    int ret = 0;
    for (int i = x; i / B == x / B && i < (int)a.size(); i++) ret += a[i];
    for (int i = x / B + 1; i < (int)b.size(); i++) ret += b[i];
    return ret;
  }
};

struct list {
  ll ans;
  std::vector<int> f;
  std::vector<std::pair<int*, int>> st1;
  std::vector<ll> st2;
  
  list(int n) : ans(0), f(n) { std::iota(f.begin(), f.end(), 0); }
  std::tuple<int, int, int, int> link(int i) {
    int s = f[i], t = f[i + 1];
    st2.emplace_back(ans);
    ans += (ll)(i - s + 1) * (t - i);
    st1.emplace_back(&f[s], f[s]), st1.emplace_back(&f[t], f[t]);
    f[s] = t, f[t] = s;
    return {s, i, i + 1, t};
  }
  void undo() {
    *st1.back().first = st1.back().second, st1.pop_back();
    *st1.back().first = st1.back().second, st1.pop_back();
    ans = st2.back(), st2.pop_back();
  }
};

template<class T, class cmp>
struct rmq {
  int n;
  std::vector<T> a;
  std::array<std::vector<T>, 20> bl;
  rmq(std::vector<T> v) {
    n = v.size(), a = v;
    bl.fill(std::vector<T>(n));
    for (int i = 0; i < n; i++) bl[0][i] = a[i];
    for (int i = 1; i < 20; i++) 
      for (int j = 0; j + (1 << i) - 1 < n; j++)
        bl[i][j] = std::min(bl[i - 1][j], bl[i - 1][j + (1 << (i - 1))], cmp());
  }
  T query(int l, int r) {
    int k = std::__lg(r - l + 1);
    return std::min(bl[k][l], bl[k][r - (1 << k) + 1], cmp());
  }
};

int main() {
  const int B = 400;
  std::cin.tie(0)->sync_with_stdio(0);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n + 1), b(n + 1);
  std::vector<std::vector<int>> pos(n + 1);
  std::vector<std::tuple<int, int, ll*>> q(m);
  std::vector<ll> ans;
  ans.reserve(m);
  for (int i = 1; i <= n; i++) std::cin >> a[i], pos[a[i]].emplace_back(i);
  for (int i = 1; i <= n; i++) std::cin >> b[i];
  for (auto &[l, r, it] : q) {
    std::cin >> l >> r;
    ans.push_back(0);
    it = &ans.back();
  }
  rmq<int, std::less<int>> bmn(b);
  rmq<int, std::greater<int>> bmx(b);
  std::vector<std::pair<int, int>> e;
  for (int i = 1; i < n; i++) e.emplace_back(std::max(b[i], b[i + 1]), i);
  std::sort(e.begin(), e.end());
  std::sort(q.begin(), q.end(), [](auto x, auto y) {
    return std::get<1>(x) < std::get<1>(y);
  });
  auto it = q.begin();
  list l(n + 1);
  array<400> cnt(n + 1);

  for (auto [v, i] : e) {
    while (it != q.end() && std::get<1>(*it) < v)  {
      *std::get<2>(*it) += cnt.query(std::get<0>(*it)), it++;
    }
    auto [l1, r1, l2, r2] = l.link(i);
    if (r1 - l1 > r2 - l2) std::swap(l1, l2), std::swap(r1, r2);
    for (int i = l1; i <= r1; i++) {
      if (pos[a[i]].size() > B) continue;
      auto it = std::lower_bound(pos[a[i]].begin(), pos[a[i]].end(), l2);
      while (it != pos[a[i]].end() && *it <= r2) 
        cnt.add(bmn.query(std::min(i, *it), std::max(i, *it)));
        
    }
  }
  while (it != q.end()) {
    *std::get<2>(*it) += cnt.query(std::get<0>(*it)), it++;
  }
  for (int i = 1; i <= n; i++) {
    if (pos[i].size() <= B) continue;
    std::vector<int> val{1, n};
    std::vector<std::tuple<int, int, int>> e;
    for (int j = 0; j + 1 < (int)pos[i].size(); j++) {
      int l = bmn.query(pos[i][j], pos[i][j + 1]), r = bmx.query(pos[i][j], pos[i][j + 1]);
      val.push_back(l), val.push_back(r), e.emplace_back(j, l, r);
    }
    std::sort(val.begin(), val.end());
    val.erase(std::unique(val.begin(), val.end()), val.end());
    std::vector<int> fi(n + 1, -1), la(n + 1, -1);
    for (int i = 0; i < (int)val.size(); i++) fi[val[i]] = la[val[i]] = i;
    for (int i = n; i >= 1; i--) if (fi[i] == -1) fi[i] = fi[i + 1];
    for (int i = 1; i <= n; i++) if (la[i] == -1) la[i] = la[i - 1];
    int B = val.size() / 500;
    std::vector<std::vector<std::tuple<int, int, ll*>>> qb((val.size() - 1) / B + 1);
    cpp_dump(val);
    for (auto [l, r, it] : q) {
      l = fi[l], r = la[r];
      qb[l / B].emplace_back(l, r, it);
    }
    std::vector<std::vector<std::pair<int, int>>> eb(val.size());
    for (auto [i, l, r] : e) {
      l = fi[l], r = la[r];
      eb[l].emplace_back(r, i);
      eb[r].emplace_back(l, i);
    }
    list li(val.size());
    for (int i = 0; i < (int)qb.size(); i++) {
      auto &cq = qb[i];
      int l = (i + 1) * B, r = l - 1, cc = 0;
      auto add = [&](int l, int r, int i) {
        int ret = 0;
        for (auto [j, v] : eb[i])
          if (l <= j && j <= r) li.link(v), ret++;
        return ret;
      };
      for (auto [ql, qr, it] : cq) {
        if (qr < (i + 1) * B) {
          int l = ql, r = l - 1, c = 0;
          while (r < qr) ++r, c += add(l, r, r);
          *it += li.ans;
          while (c--) li.undo();
          continue;
        }
        int c = 0;
        while (r < qr) ++r, cc += add(l, r, r);
        while (l > ql) --l, c += add(l, r, l);
        *it += li.ans;
        while (c--) li.undo();
        l = (i + 1) * B;
      }
      while (cc--) li.undo();
    }
  }
  for (int i = 0; i < m; i++) std::cout << ans[i] << '\n';
  
}