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;
inline long long read() {
  long long x = 0;
  char ch = getchar();
  bool f = 0;
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = 1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return f ? -x : x;
}
void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) write(x / 10);
  putchar(x % 10 + '0');
}
void writeln(long long x) {
  write(x);
  puts("");
}
void writep(long long x) {
  write(x);
  putchar(' ');
}
const int N = 1e6 + 5;
int n, m, opt, a[N], ql[N], qr[N], L[N], R[N], S[N], top;
long long ans[N];
void init() {
  for (int i = (int)(1); i <= (int)(n); i++) {
    while (top && a[S[top]] < a[i]) R[S[top--]] = i;
    S[++top] = i;
  }
  for (int i = (int)(1); i <= (int)(top); i++) R[S[i]] = n + 1;
  top = 0;
  memset(S, 0, sizeof(S));
  for (int i = (int)(n); i >= (int)(1); i--) {
    while (top && a[S[top]] < a[i]) L[S[top--]] = i;
    S[++top] = i;
  }
}
struct info {
  int pos, l, r, id, op;
} q[N << 1];
bool cmp(info a, info b) { return a.pos < b.pos; }
struct tree {
  int cnt[N << 2];
  long long sum[N << 2];
  void change(int k, int l, int r, int pos) {
    cnt[k]++;
    sum[k] += pos;
    if (l == r) return;
    int mid = l + r >> 1;
    if (pos <= mid)
      change(k << 1, l, mid, pos);
    else
      change(k << 1 | 1, mid + 1, r, pos);
  }
  pair<int, long long> merge(pair<int, long long> x, pair<int, long long> y) {
    return make_pair(x.first + y.first, x.second + y.second);
  }
  pair<int, long long> find(int k, int l, int r, int L, int R) {
    if (l >= L && r <= R) return make_pair(cnt[k], sum[k]);
    int mid = l + r >> 1;
    if (R <= mid) return find(k << 1, l, mid, L, R);
    if (L > mid) return find(k << 1 | 1, mid + 1, r, L, R);
    return merge(find(k << 1, l, mid, L, R),
                 find(k << 1 | 1, mid + 1, r, L, R));
  }
} tl, tr;
int main() {
  n = read();
  m = read();
  for (int i = (int)(1); i <= (int)(n); i++) a[i] = read();
  init();
  for (int i = (int)(1); i <= (int)(m); i++) ql[i] = read();
  for (int i = (int)(1); i <= (int)(m); i++) qr[i] = read();
  for (int i = (int)(1); i <= (int)(m); i++) {
    if (ql[i] != 1) q[++opt] = (info){ql[i] - 1, ql[i], qr[i], i, -1};
    q[++opt] = (info){qr[i], ql[i], qr[i], i, 1};
  }
  sort(q + 1, q + opt + 1, cmp);
  int now = 1;
  for (int i = (int)(1); i <= (int)(n); i++) {
    if (now > opt) break;
    tl.change(1, 0, n + 1, L[i] + 1);
    tr.change(1, 0, n + 1, R[i] - 1);
    while (now <= opt && q[now].pos == i) {
      long long res = 0;
      int l = q[now].l, r = q[now].r, op = q[now].op;
      pair<int, long long> A, B;
      A = tr.find(1, 0, n + 1, r + 1, n + 1);
      B = tr.find(1, 0, n + 1, 0, r);
      res += (long long)r * A.first + B.second;
      A = tl.find(1, 0, n + 1, 0, l - 1);
      B = tl.find(1, 0, n + 1, l, n + 1);
      res -= (long long)l * A.first + B.second;
      ans[q[now].id] += op * res;
      now++;
    }
  }
  for (int i = (int)(1); i <= (int)(m); i++) writep(ans[i] + qr[i] - ql[i] + 1);
}