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;
template <typename T>
ostream& operator<<(ostream& s, vector<T> const& v) {
  s << '{';
  for (int i = 0; i < int(v.size()); i++) s << (i ? "," : "") << v[i];
  return s << '}';
}
template <typename S, typename T>
ostream& operator<<(ostream& s, pair<S, T> const& p) {
  return s << '(' << p.first << ',' << p.second << ')';
}
int N, Q, A[1000000];
struct QR {
  int l, r;
};
vector<QR> rge;
void getRge(bool l) {
  vector<int> stk;
  for (int n = l ? 0 : N - 1; n >= 0 && n < N;) {
    while (!stk.empty() && A[stk.back()] < A[n]) stk.pop_back();
    int& a = l ? rge[n].l : rge[n].r;
    if (stk.empty()) {
      a = l ? 0 : N - 1;
    } else {
      a = l ? stk.back() + 1 : stk.back() - 1;
    }
    stk.push_back(n);
    if (l)
      ++n;
    else
      --n;
  }
}
constexpr int FTN = 1000005;
long long f1[FTN], f2[FTN];
long long sum(long long* f, int n) {
  long long a = 0;
  while (n) {
    a += f[n];
    n -= (n & -n);
  }
  return a;
}
void upd(long long* f, int n, long long v) {
  while (n < FTN) {
    f[n] += v;
    n += (n & -n);
  }
}
long long rsum(int n) { return sum(f1, n) * n - sum(f2, n); }
int main() {
  scanf("%d%d", &N, &Q);
  for (int n = 0; n < int(N); n++) scanf("%d", A + n);
  rge.resize(N);
  getRge(true);
  getRge(false);
  vector<QR> qrs(Q);
  vector<pair<int, int> > lq, rq;
  for (int q = 0; q < int(Q); q++) {
    int x;
    scanf("%d", &x);
    --x;
    if (x > 0) lq.emplace_back(x - 1, q);
    qrs[q].l = x;
  }
  for (int q = 0; q < int(Q); q++) {
    int x;
    scanf("%d", &x);
    --x;
    rq.emplace_back(x, q);
    qrs[q].r = x;
  }
  sort(begin(lq), end(lq));
  sort(begin(rq), end(rq));
  vector<long long> ans(Q);
  int lp = 0, rp = 0;
  for (int n = 0; n < int(N); n++) {
    QR qr = rge[n];
    upd(f1, qr.l + 1, 1);
    upd(f1, qr.r + 2, -1);
    upd(f2, qr.l + 1, qr.l);
    upd(f2, qr.r + 2, -(qr.r + 1));
    for (; lp < ((int)(lq).size()) && lq[lp].first == n; ++lp) {
      int q = lq[lp].second;
      ans[q] -= rsum(qrs[q].r + 1) - rsum(qrs[q].l);
    }
    for (; rp < ((int)(rq).size()) && rq[rp].first == n; ++rp) {
      int q = rq[rp].second;
      ans[q] += rsum(qrs[q].r + 1) - rsum(qrs[q].l);
    }
  }
  for (int q = 0; q < int(Q); q++)
    printf("%lld%c", ans[q], q == Q - 1 ? '\n' : ' ');
}