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;
struct InputReader {
  char buf[1000001];
  int p;
  inline InputReader() { p = 1000001; }
  inline void Flush() {
    p = 0;
    fread(buf, 1, 1000001, stdin);
  }
  inline char C() {
    if (p >= 1000001) Flush();
    return buf[p++];
  }
  inline char Readnum() {
    char ch = C();
    while (!isdigit(ch) && ch != '-') ch = C();
    return ch;
  }
  inline void Readalpha(char &c) {
    c = C();
    while (!isalpha(c)) c = C();
  }
  int operator()() {
    int ans = 0, fu = 1;
    char ch = Readnum();
    if (ch == '-') fu = -1, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10 + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  long long Readll() {
    long long ans = 0LL, fu = 1LL;
    char ch = Readnum();
    if (ch == '-') fu = -1LL, ch = C();
    while (ch >= '0' && ch <= '9') {
      ans = ans * 10LL + ch - '0';
      ch = C();
    }
    return ans * fu;
  }
  inline void Readstring(string &x) {
    x.clear();
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch) && ch != '#' && ch != '.') ch = C();
    while (isdigit(ch) || isalpha(ch) || ch == '#' || ch == '.') {
      x += ch;
      ch = C();
    }
  }
  inline void Readchstring(char s[]) {
    int len = 0;
    char ch = C();
    while (!isdigit(ch) && !isalpha(ch)) ch = C();
    while (isdigit(ch) || isalpha(ch)) {
      s[len++] = ch;
      ch = C();
    }
    s[len] = '\0';
  }
  inline void Specialread(char &c) {
    c = C();
    while (!isdigit(c) && !isalpha(c) && c != '#' && c != '.' && c != '=' &&
           c != 'B')
      c = C();
  }
} In;
inline void Read(int &x) { x = In(); }
inline void Read(int &x, int &y) {
  x = In();
  y = In();
}
inline void Read(int &x1, int &x2, int &x3) {
  x1 = In();
  x2 = In();
  x3 = In();
}
inline void Read(int &x1, int &x2, int &x3, int &x4) {
  x1 = In();
  x2 = In();
  x3 = In();
  x4 = In();
}
inline void Read(long long &x) { x = In.Readll(); }
inline void Read(long long &x, long long &y) {
  x = In.Readll();
  y = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
}
inline void Read(long long &x1, long long &x2, long long &x3, long long &x4) {
  x1 = In.Readll();
  x2 = In.Readll();
  x3 = In.Readll();
  x4 = In.Readll();
}
inline void FILEIO() {}
inline void FILEIO(string pname) {
  freopen((pname + ".in").c_str(), "r", stdin);
  freopen((pname + ".out").c_str(), "w", stdout);
}
void Printtime() {}
void END() {
  Printtime();
  exit(0);
}
template <typename T>
void END(T mes) {
  cout << mes << endl;
  END();
}
template <typename T>
void Print(T a[], int s, int t, char sp = ' ', char ed = '\n') {
  if (s > t) return;
  for (int i = s; i < t; i++) cout << a[i] << sp;
  cout << a[t] << ed;
  cout.flush();
}
template <typename T>
void Print(T a, int s = 0, int t = -1, char sp = ' ', char ed = '\n') {
  if (t == -1) t = a.size() - 1;
  for (int i = s; i <= t; i++) cout << a[i] << sp;
  cout << ed;
  cout.flush();
}
int n, qu;
int a[1000010];
int ls[1000010], rs[1000010];
long long fl[1000010], fr[1000010];
struct Fenwick_Tree {
  long long tree[1000010];
  inline void Clean() { memset(tree, 0, sizeof(tree)); }
  inline void Add(int pos, long long x) {
    for (; pos <= n; pos += ((pos) & (-pos))) tree[pos] += x;
  }
  inline void Add(int l, int r, long long x) {
    Add(l, x);
    if (r != n) Add(r + 1, -x);
  }
  inline long long Sum(int pos) {
    long long ans = 0;
    for (; pos; pos -= ((pos) & (-pos))) ans += tree[pos];
    return ans;
  }
} k, b;
struct Fenwick_Tree_Min {
  int tree[1000010];
  inline void Clean() { memset(tree, 0, sizeof(tree)); }
  inline void Change(int pos, int x) {
    for (; pos <= n; pos += ((pos) & (-pos)))
      (tree[pos]) = (((tree[pos])) > ((x)) ? ((tree[pos])) : ((x)));
  }
  inline int Min(int pos) {
    int ans = 0;
    for (; pos; pos -= ((pos) & (-pos)))
      (ans) = (((ans)) > ((tree[pos])) ? ((ans)) : ((tree[pos])));
    return ans;
  }
} lastapp;
struct Query {
  int l, r, id;
};
vector<Query> queries;
int lastpos[1000010];
inline void Init() {
  lastapp.Clean();
  k.Clean();
  b.Clean();
}
void Solve(int a[1000010], vector<Query> &queries, long long ansl[1000010]) {
  for (int(i) = 1; (i) <= (n); ++(i)) {
    lastpos[i] = lastapp.Min(n - a[i] + 1);
    lastapp.Change(n - a[i] + 1, i);
  }
  sort(queries.begin(), queries.end(),
       [](const Query &a, const Query &b) { return a.r < b.r; });
  int i = 0;
  for (auto &q : queries) {
    int ur = q.r, ul = q.l;
    while (i < ur) {
      ++i;
      k.Add(lastpos[i] + 1, i - 1, -1);
      b.Add(lastpos[i] + 1, i - 1, i);
      b.Add(1, lastpos[i], i - lastpos[i] - 1);
    }
    ansl[q.id] = k.Sum(ul) * ul + b.Sum(ul);
  }
}
int main() {
  FILEIO();
  Read(n, qu);
  for (int(i) = 1; (i) <= (n); ++(i)) Read(a[i]);
  for (int(i) = 1; (i) <= (qu); ++(i)) Read(ls[i]);
  for (int(i) = 1; (i) <= (qu); ++(i)) Read(rs[i]);
  for (int(i) = 1; (i) <= (qu); ++(i)) queries.push_back({ls[i], rs[i], i});
  Solve(a, queries, fl);
  Init();
  reverse(a + 1, a + 1 + n);
  queries.clear();
  for (int(i) = 1; (i) <= (qu); ++(i))
    queries.push_back({n - rs[i] + 1, n - ls[i] + 1, i});
  Solve(a, queries, fr);
  for (int(i) = 1; (i) <= (qu); ++(i)) {
    long long tans = rs[i] - ls[i] + 1 + fl[i] + fr[i];
    printf("%lld ", tans);
  }
  putchar(10);
  END();
}