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 MAX_N = 1 << 20;
long long tree[2 * MAX_N];
long long sum[2 * MAX_N];
int cnt[2 * MAX_N];
int pos[2 * MAX_N];
vector<int> vals[2 * MAX_N];
long long get(int node, int low, int high, int nlow, int nhigh, int t) {
  if (nhigh < low || nlow > high) return 0;
  if (low >= nlow && high <= nhigh) {
    if (t == -1) {
      if (pos[node] == -2) pos[node] = 0;
      while (pos[node] < vals[node].size() && vals[node][pos[node]] < nlow) {
        sum[node] += vals[node][pos[node]] * -1;
        ++cnt[node];
        ++pos[node];
      }
      return tree[node] - sum[node] - (long long)cnt[node] * nlow;
    } else {
      if (pos[node] == -2) pos[node] = vals[node].size() - 1;
      while (pos[node] >= 0 && vals[node][pos[node]] >= nhigh) {
        sum[node] += vals[node][pos[node]];
        ++cnt[node];
        --pos[node];
      }
      return sum[node] - (long long)cnt[node] * nhigh;
    }
  }
  int mid = (low + high) / 2;
  long long ret = 0;
  ret += get(node * 2 + 1, low, mid, nlow, nhigh, t);
  ret += get(node * 2 + 2, mid + 1, high, nlow, nhigh, t);
  return ret;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  vector<int> l(n);
  vector<int> r(n);
  for (auto& x : a) cin >> x;
  vector<int> stk;
  stk.clear();
  for (int i = 0; i < n; ++i) {
    while (stk.size() > 0 && a[stk.back()] < a[i]) stk.pop_back();
    if (stk.size() == 0)
      l[i] = 0;
    else
      l[i] = stk.back() + 1;
    stk.push_back(i);
  }
  stk.clear();
  for (int i = n - 1; i >= 0; --i) {
    while (stk.size() > 0 && a[stk.back()] < a[i]) stk.pop_back();
    if (stk.size() == 0)
      r[i] = n - 1;
    else
      r[i] = stk.back() - 1;
    stk.push_back(i);
  }
  for (int i = 0; i < n; ++i) {
    tree[MAX_N - 1 + i] = r[i] - l[i] + 1;
    vals[MAX_N - 1 + i].push_back(l[i]);
  }
  for (int i = MAX_N - 2; i >= 0; --i) {
    tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
    vals[i].resize(vals[2 * i + 1].size() + vals[2 * i + 2].size());
    int p1 = 0;
    int p2 = 0;
    int nxt = 0;
    while (p1 < vals[2 * i + 1].size() || p2 < vals[2 * i + 2].size()) {
      if (p1 == vals[2 * i + 1].size()) {
        vals[i][nxt++] = vals[2 * i + 2][p2++];
      } else if (p2 == vals[2 * i + 2].size()) {
        vals[i][nxt++] = vals[2 * i + 1][p1++];
      } else {
        if (vals[2 * i + 1][p1] < vals[2 * i + 2][p2]) {
          vals[i][nxt++] = vals[2 * i + 1][p1++];
        } else {
          vals[i][nxt++] = vals[2 * i + 2][p2++];
        }
      }
    }
  }
  vector<pair<pair<int, int>, int>> inters(q);
  vector<long long> res(q, 0);
  for (int i = 0; i < q; ++i) {
    cin >> inters[i].first.first;
    inters[i].first.first--;
  }
  for (int i = 0; i < q; ++i) {
    cin >> inters[i].first.second;
    inters[i].first.second--;
  }
  for (int i = 0; i < q; ++i) inters[i].second = i;
  for (int i = 0; i < 2 * MAX_N; ++i) {
    sum[i] = 0;
    cnt[i] = 0;
    pos[i] = -2;
  }
  sort(inters.begin(), inters.end());
  for (int i = 0; i < q; ++i) {
    res[inters[i].second] +=
        get(0, 0, MAX_N - 1, inters[i].first.first, inters[i].first.second, -1);
  }
  for (int i = 0; i < 2 * MAX_N; ++i) {
    sum[i] = 0;
    cnt[i] = 0;
    pos[i] = -2;
  }
  for (int i = 0; i < n; ++i) {
    tree[MAX_N - 1 + i] = r[i] - l[i] + 1;
    vals[MAX_N - 1 + i][0] = r[i];
  }
  for (int i = MAX_N - 2; i >= 0; --i) {
    tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
    vals[i].resize(vals[2 * i + 1].size() + vals[2 * i + 2].size());
    int p1 = 0;
    int p2 = 0;
    int nxt = 0;
    while (p1 < vals[2 * i + 1].size() || p2 < vals[2 * i + 2].size()) {
      if (p1 == vals[2 * i + 1].size()) {
        vals[i][nxt++] = vals[2 * i + 2][p2++];
      } else if (p2 == vals[2 * i + 2].size()) {
        vals[i][nxt++] = vals[2 * i + 1][p1++];
      } else {
        if (vals[2 * i + 1][p1] < vals[2 * i + 2][p2]) {
          vals[i][nxt++] = vals[2 * i + 1][p1++];
        } else {
          vals[i][nxt++] = vals[2 * i + 2][p2++];
        }
      }
    }
  }
  sort(inters.begin(), inters.end(),
       [](pair<pair<int, int>, int> i, pair<pair<int, int>, int> j) {
         return i.first.second > j.first.second;
       });
  for (int i = 0; i < q; ++i) {
    res[inters[i].second] -=
        get(0, 0, MAX_N - 1, inters[i].first.first, inters[i].first.second, 1);
  }
  for (int i = 0; i < q; ++i) cout << res[i] << " ";
  cout << endl;
  return 0;
}