#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z, k, w, q;
int A[1000005], L[1000005], R[1000005];
pair<pair<int, int>, int> Q[1000005];
vector<int> v, update[1000005];
long long bitsum[1000005], bitcnt[1000005], res[1000005];
void add(int pos, int val) {
  for (int i = pos; i <= n; i += (i & -i)) bitsum[i] += val, bitcnt[i]++;
}
int querycnt(int l, int r) {
  int res = 0;
  for (int i = r; i > 0; i -= (i & -i)) res += bitcnt[i];
  for (int i = l - 1; i > 0; i -= (i & -i)) res -= bitcnt[i];
  return res;
}
long long querysum(int l, int r) {
  long long res = 0;
  for (int i = r; i > 0; i -= (i & -i)) res += bitsum[i];
  for (int i = l - 1; i > 0; i -= (i & -i)) res -= bitsum[i];
  return res;
}
int find(int x) {
  int high = v.size();
  int low = 0;
  if (v.empty() || x > A[v[0]]) return 0;
  while (high - low > 1) {
    int mid = (high + low) / 2;
    if (A[v[mid]] > x)
      low = mid;
    else
      high = mid;
  }
  return v[low];
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = (1); i <= (n); i++) scanf("%d", &A[i]);
  for (int i = (1); i <= (n); i++) {
    L[i] = find(A[i]);
    while (v.size() > 0 && A[i] > A[v.back()]) v.pop_back();
    v.push_back(i);
  }
  v.clear();
  for (int i = (n); i >= (1); i--) {
    R[i] = find(A[i]);
    if (R[i] == 0) R[i] = n + 1;
    while (v.size() > 0 && A[i] > A[v.back()]) v.pop_back();
    v.push_back(i);
  }
  for (int i = (0); i < (q); i++) scanf("%d", &Q[i].first.first);
  for (int i = (0); i < (q); i++)
    scanf("%d", &Q[i].first.second), Q[i].second = i;
  for (int i = (1); i <= (n); i++) update[L[i]].push_back(i);
  sort(Q, Q + q);
  memset(bitsum, 0, sizeof(bitsum));
  memset(bitcnt, 0, sizeof(bitcnt));
  int x = q - 1;
  for (int i = (n); i >= (1); i--) {
    for (int j : update[i]) add(j, i);
    while (x >= 0 && Q[x].first.first == i) {
      int id = Q[x].second;
      int l = Q[x].first.first;
      int r = Q[x].first.second;
      int cnt = querycnt(l, r);
      long long sum = querysum(l, r);
      sum += 1ll * (r - l + 1 - cnt) * (l - 1);
      res[id] -= sum;
      x--;
    }
  }
  for (int i = (0); i <= (n); i++) update[i].clear();
  for (int i = (1); i <= (n); i++) update[R[i]].push_back(i);
  memset(bitsum, 0, sizeof(bitsum));
  memset(bitcnt, 0, sizeof(bitcnt));
  x = 0;
  for (int i = (0); i < (q); i++) swap(Q[i].first.first, Q[i].first.second);
  sort(Q, Q + q);
  for (int i = (0); i < (q); i++) swap(Q[i].first.first, Q[i].first.second);
  for (int i = (1); i <= (n); i++) {
    for (int j : update[i]) add(j, i);
    while (x < q && Q[x].first.second == i) {
      int id = Q[x].second;
      int l = Q[x].first.first;
      int r = Q[x].first.second;
      int cnt = querycnt(l, r);
      long long sum = querysum(l, r);
      sum += 1ll * (r - l + 1 - cnt) * (r + 1);
      res[id] += sum;
      res[id] -= (r - l + 1);
      x++;
    }
  }
  for (int i = (0); i < (q); i++) printf("%lld\n", res[i]);
  return 0;
}
