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;
using ll = long long;
template <int n, class... T>
typename enable_if<(n >= sizeof...(T))>::type __output_tuple(
    ostream &, tuple<T...> const &) {}
template <int n, class... T>
typename enable_if<(n < sizeof...(T))>::type __output_tuple(
    ostream &os, tuple<T...> const &t) {
  os << (n == 0 ? "" : ", ") << get<n>(t);
  __output_tuple<n + 1>(os, t);
}
template <class... T>
ostream &operator<<(ostream &os, tuple<T...> const &t) {
  os << "(";
  __output_tuple<0>(os, t);
  os << ")";
  return os;
}
template <class T, class U>
ostream &operator<<(ostream &os, pair<T, U> const &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
ostream &operator<<(ostream &os, const stack<T> &a) {
  os << "{";
  for (auto tmp = a; tmp.size(); tmp.pop())
    os << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  os << "}";
  return os;
}
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> a) {
  os << "{ (top) ";
  while (a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <class T, class Container>
ostream &operator<<(ostream &os, queue<T, Container> a) {
  os << "{ ";
  while (a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop();
  os << " }";
  return os;
}
template <class T,
          class = typename iterator_traits<decltype(begin(T()))>::value_type,
          class = typename enable_if<!is_same<T, string>::value>::type>
ostream &operator<<(ostream &os, const T &a) {
  for (auto ite = begin(a); ite != end(a); ++ite)
    os << (ite == begin(a) ? "" : " ") << *ite;
  return os;
}
template <class T = ll>
struct BIT {
  int n, m;
  T identity;
  vector<T> data;
  BIT() : n(0) {}
  BIT(int n, T identity = T()) : n(n), identity(identity), data(n, identity) {
    m = 1;
    while (m < n) m <<= 1;
  }
  void add(int i, T x) {
    i++;
    while (i <= n) {
      data[i - 1] = data[i - 1] + x;
      i += i & -i;
    }
  }
  T sum(int i) {
    if (i < 0) return identity;
    if (i >= n) i = n - 1;
    i++;
    T s = identity;
    while (i > 0) {
      s = s + data[i - 1];
      i -= i & -i;
    }
    return s;
  }
  T get(int i) { return sum(i) - sum(i - 1); }
  T range(int a, int b) { return sum(b) - sum(a - 1); }
  int lower_bound(T w) {
    int i = 0;
    for (int k = m; k > 0; k >>= 1) {
      if (i + k <= n && data[i + k - 1] < w) w -= data[(i += k) - 1];
    }
    return i;
  }
};
constexpr int N = 1e6 + 1;
int a[N];
int n, q;
int l[N], r[N];
ll ans[N];
void calc() {
  int rev[N], nxt[N];
  for (int i = 0; i < n; i++) rev[a[i]] = i;
  set<int> st;
  for (int i = n; i >= 1; i--) {
    auto ite = st.lower_bound(rev[i]);
    nxt[rev[i]] = ite == st.end() ? n : *ite;
    st.insert(rev[i]);
  }
  BIT<> bit0(N), bit1(N);
  vector<vector<int>> qs(n);
  for (int i = 0; i < q; i++) qs[l[i]].emplace_back(i);
  for (int i = n - 1; i >= 0; i--) {
    bit1.add(i, 1);
    bit1.add(nxt[i], -1);
    bit0.add(i, -i);
    bit0.add(nxt[i], +i);
    bit0.add(nxt[i], nxt[i] - 1 - i);
    for (int j : qs[i]) ans[j] += bit0.sum(r[j]) + bit1.sum(r[j]) * r[j];
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> q;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < q; i++) cin >> l[i], l[i]--;
  for (int i = 0; i < q; i++) cin >> r[i], r[i]--;
  calc();
  reverse(a, a + n);
  for (int i = 0; i < q; i++)
    l[i] = n - 1 - l[i], r[i] = n - 1 - r[i], swap(l[i], r[i]);
  calc();
  for (int i = 0; i < q; i++) cout << ans[i] + r[i] - l[i] + 1 << " ";
  return 0;
}