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;
template <typename T>
void out(T x) {
  cout << x << endl;
  exit(0);
}
using ll = long long;
const int maxn = 1e6 + 5;
struct segtree {
  int n;
  vector<ll> t, o;
  void init(int _n) {
    n = _n + 10;
    t.assign(4 * n, 0);
    o.assign(4 * n, 0);
  }
  void push(int v, int tl, int tr) {
    if (!o[v]) return;
    int tm = (tl + tr) / 2;
    t[2 * v] += 1ll * (tm - tl + 1) * o[v];
    t[2 * v + 1] += 1ll * (tr - tm) * o[v];
    o[2 * v] += o[v];
    o[2 * v + 1] += o[v];
    o[v] = 0;
  }
  ll qry(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return 0;
    if (l <= tl && tr <= r) return t[v];
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return qry(2 * v, tl, tm, l, r) + qry(2 * v + 1, tm + 1, tr, l, r);
  }
  void upd(int v, int tl, int tr, int l, int r, ll dx) {
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
      t[v] += 1ll * (tr - tl + 1) * dx;
      o[v] += dx;
    } else {
      push(v, tl, tr);
      int tm = (tl + tr) / 2;
      upd(2 * v, tl, tm, l, r, dx);
      upd(2 * v + 1, tm + 1, tr, l, r, dx);
      t[v] = t[2 * v] + t[2 * v + 1];
    }
  }
};
vector<ll> solve(vector<int> a, vector<pair<int, int>> Q) {
  int n = a.size();
  int q = Q.size();
  a.insert(a.begin(), 0);
  segtree tree;
  tree.init(n);
  vector<int> nl(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    nl[i] = i - 1;
    while (nl[i] > 0 && a[nl[i]] < a[i]) {
      nl[i] = nl[nl[i]];
    }
  }
  for (int i = 1; i <= n; i++) {
    tree.upd(1, 1, n, nl[i] + 1, i, +1);
  }
  vector<pair<int, int>> qu(q);
  for (int i = 0; i < q; i++) {
    qu[i].first = -Q[i].second;
    qu[i].second = i;
  }
  sort(qu.begin(), qu.end());
  vector<ll> ans(q);
  int ub = n;
  for (auto at : qu) {
    int idx = at.second;
    int r = -at.first;
    int l = Q[idx].first;
    while (ub > r) {
      tree.upd(1, 1, n, nl[ub] + 1, ub, -1);
      --ub;
    }
    ans[idx] += tree.qry(1, 1, n, l, r);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> L(q), R(q);
  for (int i = 0; i < q; i++) {
    cin >> L[i];
  }
  for (int i = 0; i < q; i++) {
    cin >> R[i];
  }
  vector<pair<int, int>> Q(q);
  for (int i = 0; i < q; i++) {
    Q[i].first = L[i];
    Q[i].second = R[i];
  }
  auto res1 = solve(a, Q);
  reverse(a.begin(), a.end());
  vector<pair<int, int>> Q2(q);
  for (int i = 0; i < q; i++) {
    Q2[i].first = n - Q[i].second + 1;
    Q2[i].second = n - Q[i].first + 1;
  }
  auto res2 = solve(a, Q2);
  for (int i = 0; i < q; i++) {
    ll len = R[i] - L[i] + 1;
    ll cur = res1[i] + res2[i] - len;
    cout << cur << " ";
  }
  cout << endl;
  return 0;
}