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>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
ostream &operator<<(ostream &os, __int128 a) {
  char c[40], tot = 0;
  if (a < 0) os.put('-'), a = -a;
  while (a) c[tot++] = a % 10, a /= 10;
  while (tot) os.put(c[--tot] + 48);
  return os;
}
istream &operator>>(istream &is, __int128 &a) {
  register char c = is.get(), f = 0;
  if (c == '-') f = 1, c = is.get();
  for (a = 0; 47 < c && c < 58; c = is.get()) a = (a << 3) + (a << 1) + c - 48;
  f && (a = -a);
  return is;
}
template <typename T>
inline void _debug(const char *names, T &&t) {
  (cerr << names << "=" << t << '\n').flush();
}
template <typename T1, typename... T>
inline void _debug(const char *names, T1 &&t1, T &&...t) {
  const char *comma = strchr(names, ',');
  (cerr.write(names, comma - names) << "=" << t1 << ",").flush();
  _debug(comma + 1, t...);
}
const int inf = 0x3f3f3f3f;
const long long lnf = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9, PI = acos(-1.0);
const int mod1 = 1000000007, mod2 = 998244353;
bool solve(const int &CASENUM);
signed main() {
  cerr << "Program by H~S~C: \n";
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(12);
  solve(1);
  return 0;
}
const int Maxn = 1000005;
long long v[Maxn], ans[Maxn], cnt[Maxn];
long long l[Maxn], r[Maxn], val[Maxn];
long long pre[Maxn];
struct qry {
  long long l, r, i;
} que[Maxn];
inline void insert(long long p, long long v, long long c) {
  for (int i = p; i >= 1; i -= i & -i) val[i] += v, cnt[i] += c;
}
inline long long query_cnt(long long p) {
  if (p == 0) return 0;
  long long ans = 0;
  for (int i = p; i < Maxn; i += i & -i) ans += cnt[i];
  return ans;
}
inline long long query_val(long long p) {
  if (p == 0) return 0;
  long long ans = 0;
  for (int i = p; i < Maxn; i += i & -i) ans += val[i];
  return ans;
}
void calc(long long n, long long q) {
  memset(val, 0, sizeof(val));
  memset(cnt, 0, sizeof(cnt));
  sort(que + 1, que + 1 + q,
       [&](const qry &a, const qry &b) { return a.r < b.r; });
  long long ptr = 0;
  for (int i = 1; i <= (q); ++i) {
    while (ptr < que[i].r) {
      ptr++;
      long long val = ptr - l[ptr];
      pre[ptr] = pre[ptr - 1] + val;
      insert(ptr, ptr - val, 1);
      insert(l[ptr], val - ptr, -1);
    }
    long long val = pre[ptr] - pre[que[i].l - 1];
    long long cc = query_cnt(que[i].l);
    long long vv = query_val(que[i].l);
    val += vv - cc * (que[i].l - 1);
    ans[que[i].i] += val;
  }
}
bool solve(const int &CASENUM) {
  long long n, q;
  cin >> n >> q;
  for (int i = 1; i <= (n); ++i) cin >> v[i];
  for (int i = 1; i <= (q); ++i) cin >> que[i].l;
  for (int i = 1; i <= (q); ++i) cin >> que[i].r;
  for (int i = 1; i <= (q); ++i)
    que[i].i = i, ans[i] = -(que[i].r - que[i].l + 1);
  for (int i = 1; i <= (n); ++i) {
    l[i] = i - 1;
    while (l[i] >= 1 && v[l[i]] < v[i]) l[i] = l[l[i]];
  }
  for (int i = n; i >= 1; --i) {
    r[i] = i + 1;
    while (r[i] <= n && v[r[i]] < v[i]) r[i] = r[r[i]];
  }
  calc(n, q);
  for (int i = 1; i <= (n); ++i)
    l[i] = n - l[i] + 1, r[i] = n - r[i] + 1, swap(l[i], r[i]);
  reverse(l + 1, l + 1 + n), reverse(r + 1, r + 1 + n);
  for (int i = 1; i <= (q); ++i)
    que[i].l = n - que[i].l + 1, que[i].r = n - que[i].r + 1,
    swap(que[i].l, que[i].r);
  calc(n, q);
  for (int i = 1; i <= (q); ++i) cout << ans[i] << (i == q ? '\n' : ' ');
  return false;
}