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>
#pragma GCC optimize(3)
#pragma GCC optimize(2)
using namespace std;
const int maxn = 1e6 + 10;
int N, Q;
int perm[maxn];
int ql[maxn];
int qr[maxn];
vector<int> id;
int L[maxn];
int R[maxn];
long long ans[maxn];
struct sumtree {
  long long tree[maxn << 2];
  long long lazy[maxn << 2];
  void build() {
    memset(tree, 0, sizeof(tree));
    memset(lazy, 0, sizeof(lazy));
  }
  void push_down(int l, int r, int id) {
    if (l < r) {
      int mid = (l + r) >> 1;
      tree[id << 1] += lazy[id] * (mid - l + 1);
      tree[id << 1 | 1] += lazy[id] * (r - mid);
      lazy[id << 1] += lazy[id];
      lazy[id << 1 | 1] += lazy[id];
      lazy[id] = 0;
    }
  }
  long long query(int l, int r, int x, int y, int id) {
    if (l > r || l > y || r < x) return 0;
    if (l <= x && y <= r) {
      return tree[id];
    }
    int mid = (x + y) >> 1;
    push_down(x, y, id);
    if (mid < l) {
      return query(l, r, mid + 1, y, id << 1 | 1);
    }
    if (mid >= r) {
      return query(l, r, x, mid, id << 1);
    }
    return query(l, r, x, mid, id << 1) + query(l, r, mid + 1, y, id << 1 | 1);
  }
  void update(int l, int r, int x, int y, long long val, int id) {
    if (l > r || r < x || l > y) return;
    if (l <= x && y <= r) {
      tree[id] += val * (y - x + 1);
      lazy[id] += val;
    } else {
      int mid = (x + y) >> 1;
      push_down(x, y, id);
      update(l, r, x, mid, val, id << 1);
      update(l, r, mid + 1, y, val, id << 1 | 1);
      tree[id] = tree[id << 1] + tree[id << 1 | 1];
    }
  }
} T;
int main() {
  scanf("%d %d", &N, &Q);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &perm[i]);
  }
  for (int i = 1; i <= Q; ++i) {
    scanf("%d", &ql[i]);
  }
  for (int i = 1; i <= Q; ++i) {
    scanf("%d", &qr[i]);
    id.push_back(i);
  }
  vector<int> stack;
  for (int i = 1; i <= N; ++i) {
    while (!stack.empty() && perm[stack.back()] <= perm[i]) stack.pop_back();
    if (stack.empty())
      L[i] = 1;
    else
      L[i] = stack.back() + 1;
    stack.push_back(i);
  }
  stack.clear();
  for (int i = N; i >= 1; --i) {
    while (!stack.empty() && perm[stack.back()] <= perm[i]) stack.pop_back();
    if (stack.empty())
      R[i] = N;
    else
      R[i] = stack.back() - 1;
    stack.push_back(i);
  }
  sort(id.begin(), id.end(), [&](int x, int y) { return qr[x] < qr[y]; });
  T.build();
  int j = 1;
  for (int i : id) {
    while (j <= N && j <= qr[i]) {
      T.update(L[j], j, 1, N, 1, 1);
      ++j;
    }
    ans[i] += T.query(ql[i], qr[i], 1, N, 1);
  }
  sort(id.begin(), id.end(), [&](int x, int y) { return ql[x] > ql[y]; });
  T.build();
  j = N;
  for (int i : id) {
    while (j >= 1 && j >= ql[i]) {
      T.update(j, R[j], 1, N, 1, 1);
      --j;
    }
    ans[i] += T.query(ql[i], qr[i], 1, N, 1);
  }
  for (int i = 1; i <= Q; ++i) {
    printf("%lld ", ans[i] - (qr[i] - ql[i] + 1));
  }
  puts("");
}