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;
long long n, m, tt, ans[1001000], num[1001000], le[1001000], ri[1001000];
struct Node {
  long long ls, rs, sum, bj;
  void clear() { sum = bj = 0; }
} node[1001000 << 1];
vector<pair<long long, long long> > lq[1001000], rq[1001000];
void build(long long now, long long l, long long r) {
  if (l == r) return;
  long long mid = ((l + r) >> 1);
  node[now].ls = ++tt;
  build(tt, l, mid);
  node[now].rs = ++tt;
  build(tt, mid + 1, r);
}
void add(long long now, long long l, long long r, long long u, long long v,
         long long w) {
  node[now].sum += (v - u + 1) * w;
  if (u == l && r == v) {
    node[now].bj += w;
    return;
  }
  long long mid = ((l + r) >> 1);
  if (u <= mid) add(node[now].ls, l, mid, u, min(mid, v), w);
  if (mid < v) add(node[now].rs, mid + 1, r, max(u, mid + 1), v, w);
}
long long ask(long long now, long long l, long long r, long long u,
              long long v) {
  if (u == l && r == v) return node[now].sum;
  long long res = (v - u + 1) * node[now].bj, mid = ((l + r) >> 1);
  if (u <= mid) res += ask(node[now].ls, l, mid, u, min(v, mid));
  if (mid < v) res += ask(node[now].rs, mid + 1, r, max(u, mid + 1), v);
  return res;
}
int main() {
  long long i, j;
  cin >> n >> m;
  for (i = 1; i <= n; i++) scanf("%lld", &num[i]);
  for (i = 1; i <= m; i++) scanf("%lld", &le[i]);
  for (i = 1; i <= m; i++) {
    scanf("%lld", &ri[i]);
    lq[ri[i]].push_back(make_pair(le[i], i));
    rq[le[i]].push_back(make_pair(ri[i], i));
  }
  num[0] = num[n + 1] = 0x3f3f3f3f3f3f3f3f;
  for (i = 1; i <= n; i++) {
    le[i] = i - 1;
    for (; num[i] > num[le[i]]; le[i] = le[le[i]])
      ;
  }
  for (i = n; i >= 1; i--) {
    ri[i] = i + 1;
    for (; num[i] > num[ri[i]]; ri[i] = ri[ri[i]])
      ;
  }
  build(tt = 1, 1, n);
  for (i = 1; i <= n; i++) {
    add(1, 1, n, le[i] + 1, i, 1);
    for (j = 0; j < lq[i].size(); j++)
      ans[lq[i][j].second] = ask(1, 1, n, lq[i][j].first, i);
  }
  for (i = 1; i <= tt; i++) node[i].clear();
  for (i = n; i >= 1; i--) {
    if (i + 1 < ri[i]) add(1, 1, n, i + 1, ri[i] - 1, 1);
    for (j = 0; j < rq[i].size(); j++)
      ans[rq[i][j].second] += ask(1, 1, n, i, rq[i][j].first);
  }
  for (i = 1; i <= m; i++) printf("%lld ", ans[i]);
}