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 + 5;
long long tree[4 * N], lazy[4 * N];
void relax(int cn, int b, int e) {
  if (lazy[cn]) {
    tree[cn] += (e - b + 1) * lazy[cn];
    if (b != e) {
      lazy[2 * cn] += lazy[cn];
      lazy[2 * cn + 1] += lazy[cn];
    }
    lazy[cn] = 0;
  }
}
void upd(int cn, int b, int e, int i, int j, long long add) {
  relax(cn, b, e);
  if (b > j or e < i) {
    return;
  }
  int lc = 2 * cn, rc = lc + 1, mid = (b + e) / 2;
  if (b >= i and e <= j) {
    lazy[cn] += add;
    relax(cn, b, e);
    return;
  }
  upd(lc, b, mid, i, j, add);
  upd(rc, mid + 1, e, i, j, add);
  tree[cn] = tree[lc] + tree[rc];
}
long long query(int cn, int b, int e, int i, int j) {
  relax(cn, b, e);
  if (b > j or e < i) return 0LL;
  if (b >= i and e <= j) {
    return tree[cn];
  }
  int lc = 2 * cn, rc = lc + 1, mid = (b + e) / 2;
  return query(lc, b, mid, i, j) + query(rc, mid + 1, e, i, j);
}
int a[N];
int L[N];
int R[N];
vector<int> QL[N];
vector<int> QR[N];
int A[N];
int B[N];
long long res[N];
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    L[i] = 1;
    R[i] = n;
  }
  vector<int> sorted;
  for (int i = 1; i <= n; i++) {
    while (sorted.size() > 0 && a[sorted.back()] < a[i]) {
      R[sorted.back()] = i - 1;
      sorted.pop_back();
    }
    sorted.push_back(i);
  }
  sorted.clear();
  for (int i = n; i >= 1; i--) {
    while (sorted.size() > 0 && a[sorted.back()] < a[i]) {
      L[sorted.back()] = i + 1;
      sorted.pop_back();
    }
    sorted.push_back(i);
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d", &A[i]);
    QL[A[i]].push_back(i);
    res[i] = A[i] - 1;
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d", &B[i]);
    QR[B[i]].push_back(i);
    res[i] -= B[i];
  }
  for (int i = n; i >= 1; i--) {
    upd(1, 1, n, i, R[i], +1);
    for (int idx : QL[i]) {
      res[idx] += query(1, 1, n, i, B[idx]);
    }
  }
  memset(tree, 0, sizeof tree);
  memset(lazy, 0, sizeof lazy);
  for (int i = 1; i <= n; i++) {
    upd(1, 1, n, L[i], i, +1);
    for (int idx : QR[i]) {
      res[idx] += query(1, 1, n, A[idx], i);
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%lld\n", res[i]);
  }
}