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;
int n, q;
int a[1000007];
int st[1000007];
int en[1000007];
vector<pair<int, int> > v_st[1000007];
long long ans[1000007];
class Tree {
 public:
  pair<long long, int> tr[6 * 1000007];
  void init(int where, int IL, int IR) {
    tr[where] = {0, 0};
    if (IL == IR) {
      return;
    }
    int mid = (IL + IR) / 2;
    init(2 * where, IL, mid);
    init(2 * where + 1, mid + 1, IR);
  }
  void update(int where, int IL, int IR, int CURL, int CURR,
              pair<long long, int> add) {
    if (CURR < CURL) {
      return;
    }
    if (IR < CURL || CURR < IL) {
      return;
    }
    if (CURL <= IL && IR <= CURR) {
      tr[where].first += add.first, tr[where].second += add.second;
      return;
    }
    int mid = (IL + IR) / 2;
    update(2 * where, IL, mid, CURL, CURR, add);
    update(2 * where + 1, mid + 1, IR, CURL, CURR, add);
  }
  pair<long long, int> query(int where, int IL, int IR, int pos) {
    if (IR < pos || pos < IL) {
      return {0, 0};
    }
    if (IL == IR) {
      return tr[where];
    }
    int mid = (IL + IR) / 2;
    pair<long long, int> ret;
    if (pos <= mid) {
      ret = query(2 * where, IL, mid, pos);
    } else {
      ret = query(2 * where + 1, mid + 1, IR, pos);
    }
    ret = {ret.first + tr[where].first, ret.second + tr[where].second};
    return ret;
  }
};
Tree w;
void input() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= q; ++i) {
    scanf("%d", &st[i]);
  }
  for (int i = 1; i <= q; ++i) {
    scanf("%d", &en[i]);
    v_st[en[i]].push_back({st[i], i});
  }
}
void calc() {
  stack<int> st;
  a[0] = n + 1;
  st.push(0);
  w.init(1, 1, n);
  for (int i = 1; i <= n; ++i) {
    while (a[st.top()] < a[i]) {
      st.pop();
    }
    w.update(1, 1, n, 1, st.top(), {i - st.top() - 1, 0});
    w.update(1, 1, n, st.top() + 1, i, {i, 1});
    st.push(i);
    int sz = v_st[i].size();
    for (int j = 0; j < sz; ++j) {
      pair<long long, int> ret = w.query(1, 1, n, v_st[i][j].first);
      ans[v_st[i][j].second] += ret.first - 1LL * ret.second * v_st[i][j].first;
    }
  }
}
void solve() {
  calc();
  for (int i = 1; i <= (n >> 1); ++i) {
    swap(a[i], a[n - i + 1]);
  }
  for (int i = 1; i <= n; ++i) {
    v_st[i].clear();
  }
  for (int i = 1; i <= q; ++i) {
    st[i] = (n - st[i] + 1);
    en[i] = (n - en[i] + 1);
    swap(st[i], en[i]);
    v_st[en[i]].push_back({st[i], i});
  }
  calc();
  for (int i = 1; i <= q; ++i) {
    printf("%I64d ", ans[i] + (en[i] - st[i] + 1));
  }
  printf("\n");
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  return 0;
}