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 = 1e6 + 10;
struct node {
  int sum;
  long long all;
} f[N * 4], v;
pair<int, int> b[N];
long long ans[N];
int l[N], r[N], id[N];
int d[N], a[N];
int n, m;
vector<int> g[N];
void ins(int l, int r, int s, int ll, int lll) {
  f[s].sum++, f[s].all += lll;
  if (l == r) return;
  if ((l + r) / 2 >= ll)
    ins(l, (l + r) / 2, s + s, ll, lll);
  else
    ins((l + r) / 2 + 1, r, s + s + 1, ll, lll);
}
void get(int l, int r, int s, int ll, int rr) {
  if (r < ll || rr < l) return;
  if (ll <= l && r <= rr) {
    if (ll == l)
      v = f[s];
    else
      v.sum += f[s].sum, v.all += f[s].all;
    return;
  }
  get(l, (l + r) / 2, s + s, ll, rr);
  get((l + r) / 2 + 1, r, s + s + 1, ll, rr);
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    while (d[0] && a[d[d[0]]] < a[i]) d[0]--;
    if (d[0])
      l[i] = d[d[0]];
    else
      l[i] = 0;
    d[++d[0]] = i;
  }
  d[0] = 0;
  for (int i = n; i >= 1; i--) {
    while (d[0] && a[d[d[0]]] < a[i]) d[0]--;
    if (d[0])
      r[i] = d[d[0]];
    else
      r[i] = n + 1;
    d[++d[0]] = i;
  }
  for (int i = 1; i <= m; i++) scanf("%d", &b[i].first), id[i] = i;
  for (int i = 1; i <= m; i++) scanf("%d", &b[i].second);
  sort(id + 1, id + m + 1,
       [](int x, int y) { return b[x].first > b[y].first; });
  for (int i = 1; i <= n; i++) g[i].clear();
  for (int i = 1; i <= n; i++) g[l[i]].push_back(i);
  int st = n;
  for (int i = 1; i <= m; i++) {
    int x = id[i];
    while (st >= b[x].first) {
      for (auto u : g[st]) ins(1, n, 1, u, l[u]);
      st--;
    }
    get(1, n, 1, b[x].first, b[x].second);
    ans[x] -=
        v.all + 1ll * (b[x].second - b[x].first + 1 - v.sum) * (b[x].first - 1);
  }
  sort(id + 1, id + m + 1,
       [](int x, int y) { return b[x].second < b[y].second; });
  for (int i = 1; i <= n; i++) g[i].clear();
  for (int i = 1; i <= 4 * n; i++) f[i].all = f[i].sum = 0;
  for (int i = 1; i <= n; i++) g[r[i]].push_back(i);
  st = 1;
  for (int i = 1; i <= m; i++) {
    int x = id[i];
    while (st <= b[x].second) {
      for (auto u : g[st]) ins(1, n, 1, u, r[u]);
      st++;
    }
    get(1, n, 1, b[x].first, b[x].second);
    ans[x] += v.all +
              1ll * (b[x].second - b[x].first + 1 - v.sum) * (b[x].second + 1);
  }
  for (int i = 1; i <= m; i++)
    printf("%lld ", ans[i] - (b[i].second - b[i].first + 1));
  return 0;
}