Problem: You are given a permutation p_1, p_2, ..., p_n. You should answer q queries. Each query is a pair (l_i, r_i), and you should calculate f(l_i, r_i).

Let's denote m_{l, r} as the position of the maximum in subsegment p_l, p_{l+1}, ..., p_r.

Then f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r) if l ≤ r or 0 otherwise.

Input

The first line contains two integers n and q (1 ≤ n ≤ 10^6, 1 ≤ q ≤ 10^6) — the size of the permutation p and the number of queries.

The second line contains n pairwise distinct integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, p_i ≠ p_j for i ≠ j) — permutation p.

The third line contains q integers l_1, l_2, ..., l_q — the first parts of the queries.

The fourth line contains q integers r_1, r_2, ..., r_q — the second parts of the queries.

It's guaranteed that 1 ≤ l_i ≤ r_i ≤ n for all queries.

Output

Print q integers — the values f(l_i, r_i) for the corresponding queries.

Example

Input


4 5
3 1 4 2
2 1 1 2 1
2 3 4 4 1


Output


1 6 8 5 1 

Note

Description of the queries: 

  1. f(2, 2) = (2 - 2 + 1) + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1; 
  2. f(1, 3) = (3 - 1 + 1) + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1) + f(1, 0) + f(2, 2) = 3 + 2 + (2 - 2 + 1) = 6; 
  3. f(1, 4) = (4 - 1 + 1) + f(1, 2) + f(4, 4) = 4 + 3 + 1 = 8; 
  4. f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + 1 + 1 = 5; 
  5. f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template <class T = int>
using V = vector<T>;
template <class T = int>
using VV = V<V<T> >;
int read_int() {
  int c, r;
  while ((c = getchar_unlocked()) < 48)
    ;
  r = c - 48;
  while ((c = getchar_unlocked()) > 47) r = r * 10 + c - 48;
  return r;
}
void write_int(lint x) {
  int b[12], *p = b;
  do *p++ = 48 + x % 10, x /= 10;
  while (x);
  do putchar_unlocked(*--p);
  while (p > b);
}
struct MinSegmentTree {
  using T = int;
  static T op(const T& x, const T& y) { return min(x, y); }
  static constexpr T e() { return 1e9; }
  const int n;
  V<T> t;
  MinSegmentTree(int n, const T& a) : n(n), t(2 * n, a) { build(); }
  T& operator[](int i) { return t[i + n]; }
  void build() {
    for (int i = n - 1; i; --i) t[i] = op(t[2 * i], t[2 * i + 1]);
  }
  T acc(int l, int r) const {
    T resl = e(), resr = e();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) resl = op(resl, t[l++]);
      if (r & 1) resr = op(t[--r], resr);
    }
    return op(resl, resr);
  }
  void set(int i, const T& x) {
    t[i += n] = x;
    while (i >>= 1) t[i] = op(t[2 * i], t[2 * i + 1]);
  }
};
struct MaxSegmentTree {
  using T = int;
  static T op(const T& x, const T& y) { return max(x, y); }
  static constexpr T e() { return -1e9; }
  const int n;
  V<T> t;
  MaxSegmentTree(int n, const T& a) : n(n), t(2 * n, a) { build(); }
  T& operator[](int i) { return t[i + n]; }
  void build() {
    for (int i = n - 1; i; --i) t[i] = op(t[2 * i], t[2 * i + 1]);
  }
  T acc(int l, int r) const {
    T resl = e(), resr = e();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) resl = op(resl, t[l++]);
      if (r & 1) resr = op(t[--r], resr);
    }
    return op(resl, resr);
  }
  void set(int i, const T& x) {
    t[i += n] = x;
    while (i >>= 1) t[i] = op(t[2 * i], t[2 * i + 1]);
  }
};
template <class T>
struct FenwickTree {
  const int n;
  V<T> t;
  FenwickTree(int n) : n(n), t(n + 1) {}
  void add(int i, T x) {
    for (++i; i <= n; i += i & -i) t[i] += x;
  }
  T sum(int i) const {
    T s = 0;
    for (; i; i -= i & -i) s += t[i];
    return s;
  }
  T sum(int l, int r) const { return sum(r) - sum(l); }
};
template <class T>
struct AddSumTree {
  const int n;
  FenwickTree<T> d, e;
  AddSumTree(int n) : n(n), d(n), e(n) {}
  void add(int l, int r, T x) {
    d.add(l, x), e.add(l, l * x);
    if (r < n) d.add(r, -x), e.add(r, -r * x);
  }
  T sum(int i) const { return i * d.sum(i) - e.sum(i); }
  T sum(int l, int r) const { return sum(r) - sum(l); }
};
int main() {
  int n = read_int(), q = read_int();
  V<> p(n);
  for (auto&& e : p) e = read_int() - 1;
  V<> ls(q);
  for (auto&& e : ls) e = read_int() - 1;
  V<> rs(q);
  for (auto&& e : rs) e = read_int() - 1;
  struct Q {
    int id, l, r;
  };
  VV<Q> ql(n), qr(n);
  V<lint> res(q);
  for (int id = 0; id < q; ++id) {
    ql[rs[id]].emplace_back(Q{id, ls[id], rs[id]});
    qr[ls[id]].emplace_back(Q{id, ls[id], rs[id]});
    res[id] = -(rs[id] - ls[id] + 1);
  }
  V<> il(n);
  MaxSegmentTree mxst(n, -1);
  for (int i = 0; i < n; ++i) {
    il[i] = mxst.acc(p[i], n);
    mxst.set(p[i], i);
  }
  AddSumTree<lint> astl(n);
  for (int i = 0; i < n; ++i) {
    astl.add(il[i] + 1, i + 1, 1);
    for (const auto& e : ql[i]) {
      res[e.id] += astl.sum(e.l, e.r + 1);
    }
  }
  V<> ir(n);
  MinSegmentTree mnst(n, n);
  for (int i = n - 1; i >= 0; --i) {
    ir[i] = mnst.acc(p[i], n);
    mnst.set(p[i], i);
  }
  AddSumTree<lint> astr(n);
  for (int i = n - 1; i >= 0; --i) {
    astr.add(i, ir[i], 1);
    for (const auto& e : qr[i]) {
      res[e.id] += astr.sum(e.l, e.r + 1);
    }
  }
  for (int id = 0; id < q; ++id) {
    if (id) putchar_unlocked(' ');
    write_int(res[id]);
  }
  putchar_unlocked('\n');
}