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>
std::vector<uint32_t> perm;
const uint32_t INF = 1e9;
struct Node {
  uint32_t lI, rI;
  uint32_t mV;
  uint32_t depth;
  Node *p, *lP, *rP;
  std::vector<Node *> binL;
  Node *l, *r;
  uint64_t subAns;
  uint32_t lD, rD;
  uint64_t rRSum, lLSum;
  Node()
      : depth(0),
        p(nullptr),
        lP(nullptr),
        rP(nullptr),
        l(nullptr),
        r(nullptr),
        lD(0),
        rD(0),
        rRSum(0),
        lLSum(0) {}
  void build_1() {
    if (p != nullptr) {
      binL.push_back(p);
      uint32_t i = 0;
      while (binL.back()->binL.size() > i) {
        binL.push_back(binL.back()->binL[i]);
        i++;
      }
    }
    subAns = rI + 1 - lI;
    if (l) {
      l->rP = this;
      l->lP = lP;
      l->p = this;
      l->depth = depth + 1;
      l->rD = rD + 1;
      l->lD = lD;
      l->build_1();
      subAns += l->subAns;
    }
    if (r) {
      r->lP = this;
      r->p = this;
      r->rP = rP;
      r->depth = depth + 1;
      r->lD = lD + 1;
      r->rD = rD;
      r->build_1();
      subAns += r->subAns;
    }
  }
  void build_2() {
    rRSum = rI + 1;
    if (rP) {
      rRSum += rP->rRSum;
    }
    if (r) {
      rRSum += r->subAns;
    }
    lLSum = 0;
    lLSum -= lI;
    if (lP) {
      lLSum += lP->lLSum;
    }
    if (l) {
      lLSum += l->subAns;
    }
    if (l) {
      l->build_2();
    }
    if (r) {
      r->build_2();
    }
  }
};
Node *get_lca(Node *a, Node *b) {
  if (a->depth < b->depth) {
    std::swap(a, b);
  }
  for (uint32_t i = a->binL.size() - 1; i < INF; i--) {
    if (i >= a->binL.size()) {
      continue;
    }
    if (a->binL[i]->depth >= b->depth) {
      a = a->binL[i];
    }
  }
  if (a == b) {
    return a;
  }
  for (uint32_t i = a->binL.size() - 1; i < INF; i--) {
    if (i >= a->binL.size()) {
      continue;
    }
    if (a->binL[i] != b->binL[i]) {
      a = a->binL[i];
      b = b->binL[i];
    }
  }
  return a->p;
}
std::vector<Node> nodes;
Node *build(uint32_t sI, uint32_t maxV) {
  if ((sI == perm.size()) || (perm[sI] > maxV)) {
    return nullptr;
  }
  nodes[sI].mV = perm[sI];
  nodes[sI].r = build(sI + 1, perm[sI]);
  if (nodes[sI].r) {
    nodes[sI].rI = nodes[sI].r->rI;
  }
  uint32_t nI = nodes[sI].rI + 1;
  if ((nI == perm.size()) || (perm[nI] > maxV)) {
    return &nodes[sI];
  } else {
    nodes[nI].l = &nodes[sI];
    nodes[nI].lI = nodes[sI].lI;
    return build(nI, maxV);
  }
}
uint32_t q;
void input() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  uint32_t n;
  std::cin >> n >> q;
  perm.resize(n);
  nodes.resize(n);
  for (uint32_t i = 0; i < n; i++) {
    std::cin >> perm[i];
    nodes[i].mV = perm[i];
    nodes[i].lI = nodes[i].rI = i;
  }
}
Node *root;
uint64_t ans_q(uint64_t lI, uint64_t rI) {
  lI--;
  rI--;
  Node *l = &nodes[lI];
  Node *r = &nodes[rI];
  Node *lca = get_lca(l, r);
  uint64_t ans = rI + 1 - lI;
  ans += l->rRSum - lca->rRSum;
  ans -= (l->rD - lca->rD) * lI;
  ans += r->lLSum - lca->lLSum;
  ans += (r->lD - lca->lD) * (rI + 1);
  return ans;
}
void answer_queries() {
  std::vector<uint32_t> l(q), r(q);
  for (uint32_t &i : l) {
    std::cin >> i;
  }
  for (uint32_t &i : r) {
    std::cin >> i;
  }
  for (uint32_t i = 0; i < q; i++) {
    std::cout << ans_q(l[i], r[i]) << "\n";
  }
}
int main() {
  input();
  root = build(0, 1e7);
  root->build_1();
  root->build_2();
  answer_queries();
}