#include <bits/stdc++.h>
using namespace std;
template <class T>
T sqr(const T& a) {
  return a * a;
}
const int MAXN = 2e5 + 100;
int tree[4 * MAXN], ql[MAXN], qr[MAXN], qu[MAXN], qd[MAXN], ansL[MAXN],
    ansR[MAXN], ansU[MAXN], ansD[MAXN], ansLL[MAXN], ansLD[MAXN], ansLU[MAXN],
    ansRU[MAXN], ansRD[MAXN], ones[MAXN], maxes[MAXN];
int n, q, p[MAXN];
void clearTree() {
  for (int i = 0; i < (4 * MAXN); i++) tree[i] = 0;
}
int get(int vl, int vr, int l, int r, int v) {
  if (l >= r) return 0;
  if (vl >= l && vr <= r) return tree[v];
  if (vl >= r || vr <= l) return 0;
  int vm = (vl + vr) / 2;
  return get(vl, vm, l, r, 2 * v) + get(vm, vr, l, r, 2 * v + 1);
}
void change(int vl, int vr, int pos, int v) {
  if (vl + 1 == vr) {
    tree[v] = 1;
    return;
  }
  int vm = (vl + vr) / 2;
  if (vm > pos)
    change(vl, vm, pos, 2 * v);
  else
    change(vm, vr, pos, 2 * v + 1);
  tree[v] = tree[2 * v] + tree[2 * v + 1];
}
struct Cmp {
  int kek;
  Cmp(int kek_) : kek(kek_) {}
  int operator()(pair<int, int> x, pair<int, int> y) const {
    if (!kek) return x < y;
    return x.first == y.first ? x.second < y.second : x.first > y.first;
  }
};
void run(int swapPoint, int doReverse, int* ansTo, int* que, int* qFrom,
         int* qTo, int toAdd = 0, int toAddTo = 0, int toAddFrom = 0) {
  vector<pair<int, int> > events;
  clearTree();
  for (int i = 0; i < (n); i++) {
    if (!swapPoint)
      events.push_back({i + 1, p[i]});
    else
      events.push_back({p[i], i + 1});
  }
  for (int i = 0; i < (q); i++) {
    events.push_back({que[i] + toAdd, -i});
  }
  sort((events).begin(), (events).end(), Cmp(doReverse));
  for (pair<int, int> p : events) {
    if (p.second <= 0) {
      ansTo[-p.second] = get(0, n + 1, qFrom[-p.second] + toAddFrom,
                             qTo[-p.second] + 1 + toAddTo, 1);
    } else {
      change(0, n + 1, p.second, 1);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  scanf("%d%d", &n, &q);
  for (int i = 0; i < (n); i++) {
    scanf("%d", &p[i]);
  }
  for (int i = 0; i < (q); i++) {
    scanf("%d%d%d%d", &ql[i], &qd[i], &qr[i], &qu[i]);
  }
  for (int i = 0; i < (q); i++) ones[i] = 1, maxes[i] = n;
  cerr << 123 << endl;
  run(0, 0, ansL, ql, qd, qu);
  cerr << 123 << endl;
  run(0, 1, ansR, qr, qd, qu);
  run(1, 0, ansD, qd, ql, qr);
  run(1, 1, ansU, qu, ql, qr);
  cerr << 123 << endl;
  run(0, 0, ansLL, qr, qd, qu, 1);
  run(0, 0, ansLD, ql, ones, qd, 0, -1);
  run(0, 1, ansRD, qr, ones, qd, 0, -1);
  run(0, 0, ansLU, ql, qu, maxes, 0, 0, 1);
  run(0, 1, ansRU, qr, qu, maxes, 0, 0, 1);
  for (int i = 0; i < (q); i++) {
    long long inside = ansLL[i] - ansL[i];
    assert(ansL[i] + ansR[i] + ansU[i] + ansD[i] + ansLU[i] + ansLD[i] +
               ansRU[i] + ansRD[i] + inside ==
           n);
    printf("%lld\n", 1ll * (ansL[i] + ansR[i]) * (ansU[i] + ansD[i]) +
                         1ll * inside * (inside - 1) / 2 +
                         1ll * inside * (n - inside) +
                         1ll * (ansLD[i] + ansRD[i]) * ansU[i] +
                         1ll * (ansLU[i] + ansRU[i]) * ansD[i] +
                         1ll * (ansLU[i] + ansLD[i]) * ansR[i] +
                         1ll * (ansRU[i] + ansRD[i]) * ansL[i] +
                         1ll * ansLD[i] * ansRU[i] + 1ll * ansLU[i] * ansRD[i] +
                         1ll * ansL[i] * ansR[i] + 1ll * ansU[i] * ansD[i]);
  }
}
