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 long double PI = acos(-1);
long long power(long long b, long long e, long long m) {
  if (e == 0) return 1;
  if (e & 1) return b * power(b * b % m, e / 2, m) % m;
  return power(b * b % m, e / 2, m);
}
long long power(long long b, long long e) {
  if (e == 0) return 1;
  if (e & 1) return b * power(b * b, e / 2);
  return power(b * b, e / 2);
}
template <typename T, typename U>
static inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
static inline void amax(T &x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << '(' << p.first << "," << p.second << ')';
}
template <typename T, typename U>
pair<T, U> operator+(const pair<T, U> &p, const pair<T, U> &q) {
  return make_pair(p.first + q.first, p.second + q.second);
}
template <typename T, typename U>
pair<T, U> operator-(const pair<T, U> &p, const pair<T, U> &q) {
  return make_pair(p.first - q.first, p.second - q.second);
}
const long long N = 1000005;
template <typename T = pair<long long, pair<long long, long long>>>
class fenwick {
 public:
  T bit[N]{};
  void update(long long st, long long en, long long in, T val) {
    for (long long j = in; j <= en; j += j & -j) {
      bit[j] = bit[j] + val;
    }
  }
  T get(long long r) {
    T x{};
    while (r > 0) {
      x = x + bit[r];
      r -= r & -r;
    }
    return x;
  }
  T query(long long l, long long r) {
    T a = get(r), b = get(l - 1);
    a = a - b;
    return a;
  }
  void clear(long long l, long long r) {
    T a{};
    for (long long i = l; i <= r; ++i) bit[i] = a;
  }
};
long long a[N];
pair<long long, long long> maxl[N], maxr[N];
long long ans[N];
fenwick<> fenw;
long long _runtimeTerror_() {
  long long n, q;
  cin >> n >> q;
  for (long long i = 1; i <= n; ++i) {
    cin >> a[i];
    maxl[i].second = maxr[i].second = i;
  }
  vector<pair<pair<long long, long long>, long long>> l(q);
  for (long long i = 0; i < q; ++i) cin >> l[i].first.first;
  for (long long i = 0; i < q; ++i) {
    cin >> l[i].first.second;
    l[i].second = i;
  }
  stack<long long> st;
  st.push(1);
  for (long long i = 2; i <= n; ++i) {
    while (!st.empty() && a[st.top()] < a[i]) {
      maxr[st.top()].first = i - 1;
      st.pop();
    }
    st.push(i);
  }
  while (!st.empty()) {
    maxr[st.top()].first = n;
    st.pop();
  }
  st.push(n);
  for (long long i = n - 1; i >= 1; --i) {
    while (!st.empty() && a[st.top()] < a[i]) {
      maxl[st.top()].first = i + 1;
      st.pop();
    }
    st.push(i);
  }
  while (!st.empty()) {
    maxl[st.top()].first = 1;
    st.pop();
  }
  a[0] = 0;
  for (long long i = 1; i <= n; ++i)
    a[i] = a[i - 1] + maxr[i].first - maxl[i].first + 1;
  sort(maxl + 1, maxl + n + 1);
  sort(maxr + 1, maxr + n + 1, greater<pair<long long, long long>>());
  long long cur = 1;
  fenw.clear(0, n);
  sort(l.begin(), l.end(),
       [&](pair<pair<long long, long long>, long long> a,
           pair<pair<long long, long long>, long long> b) {
         return a.first.first < b.first.first;
       });
  for (long long i = 0; i < q; ++i) {
    while (cur <= n && maxl[cur].first <= l[i].first.first) {
      pair<long long, pair<long long, long long>> p = {
          maxl[cur].second - maxl[cur].first + 1, {maxl[cur].second, 1}};
      fenw.update(1, n, maxl[cur].second, p);
      ++cur;
    }
    ans[l[i].second] += a[l[i].first.second] - a[l[i].first.first - 1];
    auto p = fenw.query(l[i].first.first, l[i].first.second);
    long long x = p.second.first - p.second.second * (l[i].first.first - 1);
    x = p.first - x;
    ans[l[i].second] -= x;
  }
  fenw.clear(0, n);
  cur = 1;
  sort(l.begin(), l.end(),
       [&](pair<pair<long long, long long>, long long> a,
           pair<pair<long long, long long>, long long> b) {
         return a.first.second > b.first.second;
       });
  for (long long i = 0; i < q; ++i) {
    while (cur <= n && maxr[cur].first >= l[i].first.second) {
      pair<long long, pair<long long, long long>> p = {
          maxr[cur].first - maxr[cur].second + 1, {maxr[cur].second, 1}};
      fenw.update(1, n, maxr[cur].second, p);
      ++cur;
    }
    auto p = fenw.query(l[i].first.first, l[i].first.second);
    long long x = n * p.second.second - p.second.first -
                  (n - l[i].first.second) * p.second.second + p.second.second;
    x = p.first - x;
    ans[l[i].second] -= x;
  }
  for (long long i = 0; i < q; ++i) cout << ans[i] << " ";
  return 0;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long TESTS = 1;
  while (TESTS--) _runtimeTerror_();
  return 0;
}