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 ll = long long;
int const nmax = 1000000;
class SegmentTree {
 private:
  std::vector<ll> aint;
  std::vector<int> lazy;

 public:
  SegmentTree(int n) {
    aint.resize(1 + 4 * n);
    lazy.resize(1 + 4 * n);
  }
  void computenode(int node, int from, int to) {
    if (from < to) aint[node] = aint[node * 2] + aint[node * 2 + 1];
  }
  void cleannode(int node, int from, int to) {
    if (from < to) {
      int mid = (from + to) / 2;
      lazy[node * 2] += lazy[node];
      lazy[node * 2 + 1] += lazy[node];
    }
    aint[node] += 1LL * (to - from + 1) * lazy[node];
    lazy[node] = 0;
  }
  void update(int node, int from, int to, int x, int y, int val) {
    if (x == from && to == y) {
      lazy[node] += val;
      cleannode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);
      if (x <= mid)
        update(node * 2, from, mid, x, (((y) < (mid)) ? (y) : (mid)), val);
      if (mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, (((mid + 1) < (x)) ? (x) : (mid + 1)),
               y, val);
      computenode(node, from, to);
    }
  }
  ll query(int node, int from, int to, int x, int y) {
    cleannode(node, from, to);
    if (from == x && to == y)
      return aint[node];
    else {
      int mid = (from + to) / 2;
      if (x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      else if (mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y);
      else
        return query(node * 2, from, mid, x, mid) +
               query(node * 2 + 1, mid + 1, to, mid + 1, y);
    }
  }
};
int v[5 + nmax];
int nxt_left[5 + nmax], nxt_right[5 + nmax];
int queries[5 + nmax][2];
std::vector<int> event[5 + nmax];
ll sol[5 + nmax];
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  int n, q;
  std::cin >> n >> q;
  SegmentTree aint(n);
  for (int i = 1; i <= n; i++) std::cin >> v[i];
  v[0] = v[n + 1] = n + 1;
  for (int i = 1; i <= n; i++) {
    nxt_left[i] = i - 1;
    while (v[nxt_left[i]] < v[i]) nxt_left[i] = nxt_left[nxt_left[i]];
  }
  for (int i = n; 1 <= i; i--) {
    nxt_right[i] = i + 1;
    while (v[nxt_right[i]] < v[i]) nxt_right[i] = nxt_right[nxt_right[i]];
  }
  for (int i = 1; i <= q; i++) {
    std::cin >> queries[i][0];
    event[queries[i][0] - 1].push_back(i);
  }
  for (int i = 1; i <= q; i++) {
    std::cin >> queries[i][1];
    event[queries[i][1]].push_back(i);
  }
  for (int i = 1; i <= n; i++) {
    aint.update(1, 1, n, nxt_left[i] + 1, nxt_right[i] - 1, 1);
    for (int h = 0; h < event[i].size(); h++) {
      int id = event[i][h];
      int coef = 1;
      if (i != queries[id][1]) coef = -1;
      sol[id] += coef * aint.query(1, 1, n, queries[id][0], queries[id][1]);
    }
  }
  for (int i = 1; i <= q; i++) std::cout << sol[i] << " ";
  return 0;
}