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;
long long qr1[1000005], qr2[1000005];
vector<long long> vr[1000005], qr[1000005];
long long ans[1000005], ar[1000005], lr[1000005], rr[1000005];
pair<long long, pair<long long, long long>> pr[1000005];
stack<pair<long long, long long>> sr;
long long n, q;
long long getSum(long long index, long long BITree[]) {
  long long sum = 0;
  index = index + 1;
  while (index > 0) {
    sum += BITree[index];
    index -= index & (-index);
  }
  return sum;
}
void updateBIT(long long index, long long val, long long BITree[]) {
  index = index + 1;
  while (index <= n + 1) {
    BITree[index] += val;
    index += index & (-index);
  }
}
int main() {
  scanf("%lld %lld", &n, &q);
  for (int i = 1; i < n + 1; i++) {
    scanf("%lld", &ar[i]);
  }
  sr.push(make_pair(1000000000000000000ll, 0));
  for (int i = 1; i <= n; i++) {
    while (sr.top().first < ar[i]) sr.pop();
    lr[i] = sr.top().second + 1;
    sr.push(make_pair(ar[i], i));
  }
  while (!sr.empty()) sr.pop();
  sr.push(make_pair(1000000000000000000ll, n + 1));
  for (int i = n; i >= 1; i--) {
    while (sr.top().first < ar[i]) sr.pop();
    rr[i] = sr.top().second - 1;
    sr.push(make_pair(ar[i], i));
  }
  for (int i = 0; i < q; i++) {
    scanf("%lld", &pr[i].second.first);
    pr[i].first = i;
  }
  for (int i = 0; i < q; i++) {
    scanf("%lld", &pr[i].second.second);
  }
  {
    for (int i = 1; i < n + 1; i++) vr[rr[i]].push_back(i);
    for (int i = 0; i < q; i++) {
      qr[pr[i].second.second].push_back(i);
    }
    for (int i = 1; i < n + 1; i++) {
      for (int j = 0; j < vr[i].size(); j++) {
        updateBIT(vr[i][j], i, qr1);
        updateBIT(vr[i][j], 1, qr2);
      }
      for (int j = 0; j < qr[i].size(); j++) {
        long long node = qr[i][j];
        long long idx = pr[node].first, l = pr[node].second.first,
                  r = pr[node].second.second;
        ans[idx] += getSum(r, qr1) - getSum(l - 1, qr1) +
                    r * ((r - l + 1) - (getSum(r, qr2) - getSum(l - 1, qr2)));
      }
    }
  }
  for (int i = 1; i < n + 3; i++)
    vr[i].clear(), qr[i].clear(), qr1[i] = qr2[i] = 0;
  {
    for (int i = 1; i < n + 1; i++) vr[lr[i]].push_back(i);
    for (int i = 0; i < q; i++) {
      qr[pr[i].second.first].push_back(i);
    }
    for (int i = n; i >= 1; i--) {
      for (int j = 0; j < vr[i].size(); j++) {
        updateBIT(vr[i][j], i, qr1);
        updateBIT(vr[i][j], 1, qr2);
      }
      for (int j = 0; j < qr[i].size(); j++) {
        long long node = qr[i][j];
        long long idx = pr[node].first, l = pr[node].second.first,
                  r = pr[node].second.second;
        ans[idx] -= getSum(r, qr1) + l * ((r - l + 1) - getSum(r, qr2));
      }
    }
  }
  for (int i = 0; i < q; i++)
    cout << ans[i] + (pr[i].second.second - pr[i].second.first + 1) << " ";
}