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;
int N, Q;
int arr[1000005];
int lft[1000005], rht[1000005];
long long ans[1000005];
vector<int> qu[1000005];
long long bit[1000005];
void solve() {
  for (int q = 1; q <= Q; q++) {
    qu[rht[q]].emplace_back(q);
  }
  deque<int> stk = {0};
  deque<long long> pre = {0};
  long long tot = 0, instk = 0;
  for (int i = 1; i <= N; i++) {
    while (!stk.empty() && arr[stk.front()] < arr[i]) {
      int n = stk.front();
      stk.pop_front();
      pre.pop_front();
      int v = i - n - 1;
      instk -= n;
      while (n <= N) {
        bit[n] += v;
        n += n & -n;
      }
      tot += v;
    }
    stk.push_front(i);
    pre.push_front(pre.front() + i);
    instk += i;
    for (int n : qu[i]) {
      int x = lft[n] - 1;
      ans[n] += tot;
      while (x) {
        ans[n] -= bit[x];
        x -= x & -x;
      }
      int l = 0, r = stk.size() - 1, k = 0;
      while (l <= r) {
        int mid = l + r >> 1;
        if (stk[mid] >= lft[n]) {
          l = mid + 1;
          k = mid;
        } else {
          r = mid - 1;
        }
      }
      ans[n] += 1LL * (k + 1) * i - pre.front() + pre[k + 1];
    }
    qu[i].clear();
  }
  fill(bit, bit + 1 + N, 0);
}
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  arr[0] = N + 1;
  for (int i = 1; i <= N; i++) {
    cin >> arr[i];
  }
  for (int q = 1; q <= Q; q++) {
    cin >> lft[q];
  }
  for (int q = 1; q <= Q; q++) {
    cin >> rht[q];
  }
  solve();
  reverse(arr + 1, arr + 1 + N);
  for (int q = 1; q <= Q; q++) {
    rht[q] = N - rht[q] + 1;
    lft[q] = N - lft[q] + 1;
    swap(rht[q], lft[q]);
  }
  solve();
  for (int q = 1; q <= Q; q++) {
    cout << ans[q] + rht[q] - lft[q] + 1 << " ";
  }
}