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>
struct fenwick_tree {
  int tree_n = 0;
  T tree_sum = 0;
  vector<T> tree;
  fenwick_tree(int n = 0) {
    if (n > 0) init(n);
  }
  void init(int n) {
    tree_n = n;
    tree_sum = 0;
    tree.assign(tree_n + 1, 0);
  }
  void update(int index, const T &change) {
    assert(0 <= index && index < tree_n);
    tree_sum += change;
    for (int i = index + 1; i <= tree_n; i += i & -i) tree[i] += change;
  }
  T query(int count) const {
    assert(count <= tree_n);
    T sum = 0;
    for (int i = count; i > 0; i -= i & -i) sum += tree[i];
    return sum;
  }
  T query_suffix(int start) const { return tree_sum - query(start); }
  T query(int a, int b) const { return query(b) - query(a); }
};
struct query {
  int L, R, index;
  query(int _L = -1, int _R = -1, int _index = -1)
      : L(_L), R(_R), index(_index) {}
};
int N, Q;
vector<int> P;
vector<query> queries;
vector<vector<query>> queries_at_point;
vector<long long> answers;
void solve_right_half() {
  vector<int> stack(N);
  vector<long long> stack_sum(N + 1, 0);
  int S = 0;
  fenwick_tree<long long> done_tree(N);
  for (int i = 0; i < N; i++) {
    while (S > 0 && P[i] > P[stack[S - 1]]) {
      done_tree.update(stack[S - 1], i - stack[S - 1] - 1);
      S--;
    }
    stack[S] = i;
    stack_sum[S + 1] = stack_sum[S] + i;
    S++;
    for (query &q : queries_at_point[i]) {
      answers[q.index] += done_tree.query_suffix(q.L);
      int index =
          lower_bound(stack.begin(), stack.begin() + S, q.L) - stack.begin();
      answers[q.index] +=
          (long long)i * (S - index) - (stack_sum[S] - stack_sum[index]);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N >> Q;
  P.resize(N);
  queries.resize(Q);
  for (int i = 0; i < N; i++) cin >> P[i];
  for (int q = 0; q < Q; q++) queries[q].index = q;
  for (int q = 0; q < Q; q++) {
    cin >> queries[q].L;
    queries[q].L--;
  }
  for (int q = 0; q < Q; q++) {
    cin >> queries[q].R;
    queries[q].R--;
  }
  answers.assign(Q, 0);
  for (query &q : queries) answers[q.index] = q.R - q.L + 1;
  queries_at_point.assign(N, {});
  for (query &q : queries) queries_at_point[q.R].push_back(q);
  solve_right_half();
  for (query &q : queries) {
    q.L = N - 1 - q.L;
    q.R = N - 1 - q.R;
    swap(q.L, q.R);
  }
  reverse(P.begin(), P.end());
  queries_at_point.assign(N, {});
  for (query &q : queries) queries_at_point[q.R].push_back(q);
  solve_right_half();
  for (int q = 0; q < Q; q++) cout << answers[q] << (q < Q - 1 ? ' ' : '\n');
}