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 <class T>
inline void amin(T &x, const T &y) {
  if (y < x) x = y;
}
template <class T>
inline void amax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class Iter>
void rprintf(const char *fmt, Iter begin, Iter end) {
  for (bool sp = 0; begin != end; ++begin) {
    if (sp)
      putchar(' ');
    else
      sp = true;
    printf(fmt, *begin);
  }
  putchar('\n');
}
template <class T>
struct Fenwick {
  int n;
  T *d;
  Fenwick() : n(0), d(NULL) {}
  Fenwick(int n_) : n(n_) { d = new T[n_](); }
  Fenwick(const Fenwick &y) : n(y.n) {
    d = new T[n];
    memcpy(d, y.d, sizeof(T) * n);
  }
  ~Fenwick() {
    delete[] d;
    d = NULL;
    n = 0;
  }
  friend void swap(Fenwick &x, Fenwick &y) {
    swap(x.n, y.n);
    swap(x.d, y.d);
  }
  Fenwick &operator=(Fenwick y) {
    swap(*this, y);
    return *this;
  }
  inline void add(int i, const T &x) {
    for (; i < n; i |= i + 1) d[i] += x;
  }
  inline T sum(int r) {
    T s = T();
    for (; r; r &= r - 1) s += d[r - 1];
    return s;
  }
  T sum(int l, int r) { return sum(r) - sum(l); }
};
int N, Q;
int P[1000011];
int nxt[1000011], prv[1000011];
struct Query {
  int l, r, i;
} query[1000011];
struct CmpR {
  bool operator()(const Query &x, const Query &y) const { return x.r < y.r; }
} cmpR;
struct CmpL {
  bool operator()(const Query &x, const Query &y) const { return x.l < y.l; }
} cmpL;
long long ans[1000111];
void MAIN() {
  scanf("%d%d", &N, &Q);
  for (int i = 0, i_len = (N); i < i_len; ++i) scanf("%d", P + i), P[i]--;
  for (int i = 0, i_len = (Q); i < i_len; ++i) {
    int l;
    scanf("%d", &l);
    query[i].l = l - 1;
    query[i].i = i;
  }
  for (int i = 0, i_len = (Q); i < i_len; ++i) {
    int r;
    scanf("%d", &r);
    query[i].r = r;
  }
  stack<int> st;
  st.push(-1);
  for (int i = 0, i_len = (N); i < i_len; ++i) {
    while (st.top() >= 0 && P[st.top()] < P[i]) st.pop();
    prv[i] = st.top() + 1;
    st.push(i);
  }
  sort(query, query + Q, cmpL);
  vector<pair<int, int> > Z;
  Z.reserve(N);
  for (int i = 0, i_len = (N); i < i_len; ++i) Z.emplace_back(prv[i], i);
  sort(Z.begin(), Z.end());
  Fenwick<long long> S(N);
  Fenwick<int> F(N);
  for (int q = Q, pos = N - 1; q--;) {
    while (pos >= 0 && query[q].l <= Z[pos].first) {
      int idx = Z[pos].second;
      S.add(idx, Z[pos].first);
      F.add(idx, 1);
      pos--;
    }
    long long l = query[q].l;
    long long r = query[q].r;
    long long s = S.sum(l, r);
    long long c = F.sum(l, r);
    long long len = r - l;
    ans[query[q].i] -= s + (len - c) * l;
  }
  while (!st.empty()) st.pop();
  st.push(N);
  for (int i = N; i--;) {
    while (st.top() < N && P[st.top()] < P[i]) st.pop();
    nxt[i] = st.top();
    st.push(i);
  }
  sort(query, query + Q, cmpR);
  for (int i = 0, i_len = (N); i < i_len; ++i) Z[i] = make_pair(nxt[i], i);
  sort(Z.begin(), Z.end());
  S = Fenwick<long long>(N);
  F = Fenwick<int>(N);
  for (int q = 0, pos = 0; q < Q; q++) {
    while (pos < N && Z[pos].first < query[q].r) {
      int idx = Z[pos].second;
      S.add(idx, Z[pos].first);
      F.add(idx, 1);
      pos++;
    }
    long long l = query[q].l;
    long long r = query[q].r;
    long long s = S.sum(l, r);
    long long c = F.sum(l, r);
    long long len = r - l;
    ans[query[q].i] += s + (len - c) * r;
  }
  rprintf("%lld", ans, ans + Q);
}
int main() {
  int TC = 1;
  for (int tc = 0, tc_len = (TC); tc < tc_len; ++tc) MAIN();
  return 0;
}