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;
const int N = 1000005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
int n, m;
int a[N];
int l[N], r[N];
int s[N], e[N];
pair<int, int> p[N];
stack<pair<int, int> > st;
vector<int> mas[N];
pair<long long, int> t[4 * N];
long long answ[N];
pair<long long, int> tmerge(pair<long long, int> a, pair<long long, int> b) {
  pair<long long, int> c;
  c.first = a.first + b.first;
  c.second = a.second + b.second;
  return c;
}
void build(int v, int s, int e, int ii) {
  if (s == e) {
    t[v].first = ii ? r[s] : l[s];
    t[v].second = 0;
    return;
  }
  int m = (s + e) / 2;
  build(2 * v, s, m, ii);
  build(2 * v + 1, m + 1, e, ii);
  t[v] = tmerge(t[2 * v], t[2 * v + 1]);
}
void update(int v, int s, int e, int pos) {
  if (s == e) {
    t[v].first = 0;
    t[v].second = 1;
    return;
  }
  int m = (s + e) / 2;
  if (pos <= m)
    update(2 * v, s, m, pos);
  else
    update(2 * v + 1, m + 1, e, pos);
  t[v] = tmerge(t[2 * v], t[2 * v + 1]);
}
pair<long long, int> get(int v, int s, int e, int l, int r) {
  if (l > r) return make_pair(0, 0);
  if (s == l && e == r) return t[v];
  int m = (s + e) / 2;
  return tmerge(get(2 * v, s, m, l, min(r, m)),
                get(2 * v + 1, m + 1, e, max(m + 1, l), r));
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d", &s[i]);
  }
  for (int i = 1; i <= m; i++) {
    scanf("%d", &e[i]);
  }
  st.push(make_pair(inf, 0));
  for (int i = 1; i <= n; i++) {
    while ((int)st.size() && st.top().first < a[i]) {
      st.pop();
    }
    l[i] = st.top().second + 1;
    st.push(make_pair(a[i], i));
  }
  while (!st.empty()) {
    st.pop();
  }
  st.push(make_pair(inf, n + 1));
  for (int i = n; i >= 1; i--) {
    while ((int)st.size() && st.top().first < a[i]) {
      st.pop();
    }
    r[i] = st.top().second - 1;
    st.push(make_pair(a[i], i));
  }
  for (int i = 1; i <= n; i++) {
    mas[l[i]].push_back(i);
  }
  for (int i = 1; i <= m; i++) {
    p[i] = make_pair(s[i], i);
  }
  sort(p + 1, p + m + 1);
  build(1, 1, n, 0);
  int it = 1;
  for (int i = 1; i <= m; i++) {
    int x = p[i].first;
    int id = p[i].second;
    while (it != x) {
      for (int j = 0; j < (int)mas[it].size(); j++) {
        update(1, 1, n, mas[it][j]);
      }
      ++it;
    }
    pair<long long, int> P = get(1, 1, n, s[id], e[id]);
    answ[id] -= P.first + P.second * 1ll * x;
  }
  for (int i = 1; i <= n; i++) {
    mas[l[i]].clear();
  }
  for (int i = 1; i <= n; i++) {
    mas[r[i]].push_back(i);
  }
  for (int i = 1; i <= m; i++) {
    p[i] = make_pair(e[i], i);
  }
  sort(p + 1, p + m + 1);
  reverse(p + 1, p + m + 1);
  build(1, 1, n, 1);
  it = n;
  for (int i = 1; i <= m; i++) {
    int x = p[i].first;
    int id = p[i].second;
    while (it != x) {
      for (int j = 0; j < (int)mas[it].size(); j++) {
        update(1, 1, n, mas[it][j]);
      }
      --it;
    }
    pair<long long, int> P = get(1, 1, n, s[id], e[id]);
    answ[id] += P.first + P.second * 1ll * x;
  }
  for (int i = 1; i <= m; i++) {
    answ[i] += e[i] - s[i] + 1;
    printf("%lld ", answ[i]);
  }
  cout << endl;
  return 0;
}