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>
#pragma GCC optimize("O3")
using namespace std;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
const int N = 1e6 + 10;
int a[N], prevv[N], nextt[N], l[N], r[N];
long long ans[N];
vector<pair<int, int>> q1[N], q2[N];
struct ST {
  vector<long long> f1, f2;
  ST(int n) {
    f1.resize(4 * n + 10);
    f2.resize(4 * n + 10);
  }
  void push(int v) {
    f1[2 * v] += f1[v];
    f1[2 * v + 1] += f1[v];
    f1[v] = 0;
    f2[2 * v] += f2[v];
    f2[2 * v + 1] += f2[v];
    f2[v] = 0;
  }
  void update1(int v, int l, int r, int a, int b, int delta) {
    if (l > b || r < a) {
      return;
    }
    if (l >= a && r <= b) {
      f1[v] += delta;
      return;
    }
    push(v);
    int mid = (l + r) / 2;
    update1(2 * v, l, mid, a, b, delta);
    update1(2 * v + 1, mid + 1, r, a, b, delta);
  }
  void update2(int v, int l, int r, int a, int b, int delta) {
    if (l > b || r < a) {
      return;
    }
    if (l >= a && r <= b) {
      f2[v] += delta;
      return;
    }
    push(v);
    int mid = (l + r) / 2;
    update2(2 * v, l, mid, a, b, delta);
    update2(2 * v + 1, mid + 1, r, a, b, delta);
  }
  long long get(int v, int l, int r, int need) {
    if (l == r) {
      return l * f2[v] + f1[v];
    }
    int mid = (l + r) / 2;
    push(v);
    if (need <= mid) {
      return get(2 * v, l, mid, need);
    }
    return get(2 * v + 1, mid + 1, r, need);
  }
};
void source() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  vector<pair<int, int>> st;
  for (int i = n; i >= 1; i--) {
    while (!st.empty() && a[i] > st.back().first) {
      st.pop_back();
    }
    if (st.empty()) {
      nextt[i] = n + 1;
    } else {
      nextt[i] = st.back().second - 1;
    }
    st.push_back({a[i], i});
  }
  st = {};
  for (int i = 1; i <= n; i++) {
    while (!st.empty() && a[i] > st.back().first) {
      st.pop_back();
    }
    if (st.empty()) {
      prevv[i] = 0;
    } else {
      prevv[i] = st.back().second + 1;
    }
    st.push_back({a[i], i});
  }
  for (int i = 0; i < m; i++) {
    cin >> l[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> r[i];
  }
  for (int i = 0; i < m; i++) {
    q1[l[i]].push_back({r[i], i});
    q2[r[i]].push_back({l[i], i});
    ans[i] = r[i] - l[i] + 1;
  }
  ST tree(n);
  for (int i = n; i >= 1; i--) {
    tree.update1(1, 1, n, nextt[i], n, nextt[i]);
    tree.update2(1, 1, n, i, nextt[i] - 1, 1);
    for (auto it : q1[i]) {
      ans[it.second] += tree.get(1, 1, n, it.first);
    }
  }
  ST tree2(n);
  for (int i = 1; i <= n; i++) {
    tree2.update1(1, 1, n, 1, prevv[i], prevv[i]);
    tree2.update2(1, 1, n, prevv[i] + 1, i, 1);
    for (auto it : q2[i]) {
      ans[it.second] -= tree2.get(1, 1, n, it.first);
    }
  }
  for (int i = 0; i < m; i++) {
    cout << ans[i] << ' ';
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  source();
  return 0;
}