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 const maxn = 1000003;
int n = 0, m = 0;
int a[maxn];
struct Query {
  int l, r, id;
};
inline bool cmp1ofQuery(Query const &lhs, Query const &rhs) {
  return lhs.l < rhs.l;
}
inline bool cmp2ofQuery(Query const &lhs, Query const &rhs) {
  return lhs.r > rhs.r;
}
Query q[maxn];
int cl[maxn], cr[maxn];
int st[maxn], top = 0;
void getControl() {
  cl[1] = 1;
  st[top = 1] = 1;
  for (int i = 2; i <= n; ++i) {
    while (top && a[i] > a[st[top]]) cr[st[top--]] = i - 1;
    cl[i] = st[top] + 1;
    st[++top] = i;
  }
  while (top) cr[st[top--]] = n;
}
int nod[maxn];
inline bool cmp1ofNode(int a, int b) { return cl[a] < cl[b]; }
inline bool cmp2ofNode(int a, int b) { return cr[a] > cr[b]; }
long long tri[maxn], tr0[maxn];
inline int lowbit(int x) { return x & -x; }
inline void add(long long *ar, int p, int v) {
  while (p <= n) {
    ar[p] += v;
    p += lowbit(p);
  }
}
inline long long query(long long *ar, int p) {
  long long sum = 0;
  while (p > 0) {
    sum += ar[p];
    p -= lowbit(p);
  }
  return sum;
}
inline long long query(long long *ar, int l, int r) {
  return query(ar, r) - query(ar, l - 1);
}
long long ans[maxn];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 1; i <= m; ++i) scanf("%d", &q[i].l);
  for (int i = 1; i <= m; ++i) scanf("%d", &q[i].r);
  for (int i = 1; i <= m; ++i) q[i].id = i;
  getControl();
  for (int i = 1; i <= n; ++i) nod[i] = i;
  sort(nod + 1, nod + n + 1, cmp1ofNode);
  sort(q + 1, q + m + 1, cmp1ofQuery);
  int cur = 1;
  for (int i = 1; i <= n; ++i) tri[i] = tri[i - 1] + cl[i], tr0[i] = 0;
  for (int i = n; i >= 1; --i) tri[i] -= tri[i - lowbit(i)];
  for (int i = 1; i <= m; ++i) {
    while (cur <= n && cl[nod[cur]] <= q[i].l) {
      int x = nod[cur++];
      add(tri, x, -cl[x]);
      add(tr0, x, +1);
    }
    long long v =
        query(tri, q[i].l, q[i].r) + query(tr0, q[i].l, q[i].r) * q[i].l;
    ans[q[i].id] -= v;
  }
  sort(nod + 1, nod + n + 1, cmp2ofNode);
  sort(q + 1, q + m + 1, cmp2ofQuery);
  cur = 1;
  for (int i = 1; i <= n; ++i) tri[i] = tri[i - 1] + cr[i], tr0[i] = 0;
  for (int i = n; i >= 1; --i) tri[i] -= tri[i - lowbit(i)];
  for (int i = 1; i <= m; ++i) {
    while (cur <= n && cr[nod[cur]] >= q[i].r) {
      int x = nod[cur++];
      add(tri, x, -cr[x]);
      add(tr0, x, +1);
    }
    long long v =
        query(tri, q[i].l, q[i].r) + query(tr0, q[i].l, q[i].r) * q[i].r;
    ans[q[i].id] += v;
  }
  for (int i = 1; i <= m; ++i) ans[q[i].id] += q[i].r - q[i].l + 1;
  for (int i = 1; i <= m; ++i) printf("%lld ", ans[i]);
  return 0;
}