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;
namespace long_code {
template <class T>
T read() {
  T var;
  cin >> var;
  return var;
}
template <class T>
void print(T var) {
  cout << var;
}
const int BUF = 1 << 12;
char read_buf[BUF];
char write_buf[BUF];
int read_pos = 0;
int read_len = 0;
int write_pos = 0;
struct Flusher {
  ~Flusher() { fwrite(write_buf, 1, write_pos, stdout); }
} flusher;
bool is_eof() {
  if (read_pos == read_len) {
    read_len = (int)fread(read_buf, 1, BUF, stdin);
    read_pos = 0;
  }
  if (read_pos == read_len) {
    return true;
  }
  return false;
}
char get_char() {
  if (is_eof()) {
    return -1;
  }
  return read_buf[read_pos++];
}
template <>
char read<char>() {
  char c = get_char();
  while (c <= ' ') {
    c = get_char();
  }
  return c;
}
void print(char x) {
  if (write_pos == BUF) {
    fwrite(write_buf, 1, write_pos, stdout);
    write_pos = 0;
  }
  write_buf[write_pos++] = x;
}
template <>
int read<int>() {
  int sum = 0;
  char c = read<char>();
  int sign = +1;
  if (c == '-') {
    sign = -1;
    c = get_char();
  }
  while ('0' <= c && c <= '9') {
    sum = 10 * sum + c - '0';
    c = get_char();
  }
  return sum * sign;
}
template <>
long long read<long long>() {
  long long sum = 0;
  char c = read<char>();
  int sign = +1;
  if (c == '-') {
    sign = -1;
    c = get_char();
  }
  while ('0' <= c && c <= '9') {
    sum = 10 * sum + c - '0';
    c = get_char();
  }
  return sum * sign;
}
void print(int x) {
  static char s[30];
  int n = 0;
  if (x < 0) {
    print('-');
    x = -x;
  }
  while (!n || x) {
    s[n++] = (char)(x % 10 + '0');
    x /= 10;
  }
  while (--n >= 0) {
    print(s[n]);
  }
}
void print(long long x) {
  static char s[30];
  int n = 0;
  if (x < 0) {
    print('-');
    x = -x;
  }
  while (!n || x) {
    s[n++] = (char)(x % 10 + '0');
    x /= 10;
  }
  while (--n >= 0) {
    print(s[n]);
  }
}
struct Function {
  long long k, b;
  Function() : k(0), b(0) {}
  Function(long long f, long long s) : k(f), b(s) {}
  long long operator()(long long x) { return k * x + b; }
};
struct Query {
  int l;
  int r;
  int id;
  Query(int a, int b, int c) : l(a), r(b), id(c) {}
  Query() : Query(0, 0, 0) {}
};
bool operator<(Query a, Query b) { return a.r < b.r; }
}  // namespace long_code
using namespace long_code;
const int N = 2e6;
Function fen[N];
void add(int i, Function f) {
  i += 10;
  for (; i < N; i |= i + 1) {
    fen[i].k += f.k;
    fen[i].b += f.b;
  }
}
void add(int l, int r, Function f) {
  add(l, f);
  add(r + 1, {-f.k, -f.b});
}
Function sum(int i) {
  i += 10;
  Function f;
  for (; i >= 0; i = (i & (i + 1)) - 1) {
    f.k += fen[i].k;
    f.b += fen[i].b;
  }
  return f;
}
int n, m;
int a[N];
int link[N];
vector<Query> qrs;
vector<Query> by_ind[N];
long long answer[N];
void solve_left() {
  for (int i = 0; i < n; ++i) {
    by_ind[i].clear();
  }
  for (int i = 0; i < m; ++i) {
    by_ind[qrs[i].r].push_back(qrs[i]);
  }
  for (int i = 0; i < N; ++i) {
    fen[i] = Function();
  }
  for (int i = 0; i < n; ++i) {
    link[i] = i - 1;
    while (link[i] >= 0 && !(a[link[i]] > a[i])) {
      link[i] = link[link[i]];
    }
  }
  for (int i = 0; i < n; ++i) {
    add(0, link[i], {0, i - link[i] - 1});
    add(link[i] + 1, i, {-1, i});
    for (Query &q : by_ind[i]) {
      Function f = sum(q.l);
      answer[q.id] += f(q.l);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  n = read<int>();
  m = read<int>();
  for (int i = 0; i < n; ++i) {
    a[i] = read<int>();
  }
  qrs.resize(m);
  for (int i = 0; i < m; ++i) {
    qrs[i].l = read<int>() - 1;
    qrs[i].id = i;
  }
  for (int i = 0; i < m; ++i) {
    qrs[i].r = read<int>() - 1;
    answer[i] = qrs[i].r - qrs[i].l + 1;
  }
  solve_left();
  reverse(a, a + n);
  for (int i = 0; i < m; ++i) {
    qrs[i].l = n - 1 - qrs[i].l;
    qrs[i].r = n - 1 - qrs[i].r;
    swap(qrs[i].l, qrs[i].r);
  }
  solve_left();
  for (int i = 0; i < m; ++i) {
    print(answer[i]);
    print(' ');
  }
  print('\n');
  return 0;
}