#include <bits/stdc++.h>
using namespace std;
int curEmpty = 1;
int SegTree[5000007];
int LeftNode[5000007];
int RightNode[5000007];
int Roots[200007];
int createTree(int fs, int ls) {
  int cur = curEmpty++;
  if (fs == ls) {
    SegTree[cur] = 0;
    LeftNode[cur] = RightNode[cur] = -1;
    return cur;
  }
  int md = (fs + ls) / 2;
  LeftNode[cur] = createTree(fs, md);
  RightNode[cur] = createTree(md + 1, ls);
  SegTree[cur] = SegTree[LeftNode[cur]] + SegTree[RightNode[cur]];
  return cur;
}
int Persist(int fs, int ls, int cur, int key, int val) {
  if (!(fs <= key && key <= ls)) return cur;
  int curNew = curEmpty++;
  if (fs == ls) {
    SegTree[curNew] = val;
    LeftNode[curNew] = RightNode[curNew] = -1;
    return curNew;
  }
  int md = (fs + ls) / 2;
  LeftNode[curNew] = Persist(fs, md, LeftNode[cur], key, val);
  RightNode[curNew] = Persist(md + 1, ls, RightNode[cur], key, val);
  SegTree[curNew] = SegTree[LeftNode[curNew]] + SegTree[RightNode[curNew]];
  return curNew;
}
int Query(int fs, int ls, int cur, int qfs, int qls) {
  if (qfs > qls) return 0;
  if (qls < fs || ls < qfs) return 0;
  if (qfs <= fs && ls <= qls) return SegTree[cur];
  int md = (fs + ls) / 2;
  return Query(fs, md, LeftNode[cur], qfs, qls) +
         Query(md + 1, ls, RightNode[cur], qfs, qls);
}
int P[200007];
int main() {
  int i, j, k, l, d, u, m, n, w, x, y, z, a, b, r, q;
  scanf("%d", &n);
  scanf("%d", &q);
  for (i = 1; i <= n; i++) scanf("%d", &P[i]);
  Roots[0] = createTree(1, n);
  for (i = 1; i <= n; i++) {
    Roots[i] = Persist(1, n, Roots[i - 1], P[i], 1);
  }
  while (q--) {
    scanf("%d", &l);
    scanf("%d", &d);
    scanf("%d", &r);
    scanf("%d", &u);
    y = Query(1, n, Roots[n], u + 1, n) - Query(1, n, Roots[r], u + 1, n);
    x = Query(1, n, Roots[n], 1, d - 1) - Query(1, n, Roots[r], 1, d - 1);
    w = Query(1, n, Roots[l - 1], 1, d - 1);
    z = Query(1, n, Roots[l - 1], u + 1, n);
    printf("%lld\n",
           (1LL * (n) * (n - 1) / 2) -
               (1LL * (l - 1) * (l - 2) / 2 + 1LL * (n - r) * (n - r - 1) / 2 +
                1LL * (d - 1) * (d - 2) / 2 + 1LL * (n - u) * (n - u - 1) / 2 -
                1LL * (y) * (y - 1) / 2 - 1LL * (w) * (w - 1) / 2 -
                1LL * (x) * (x - 1) / 2 - 1LL * (z) * (z - 1) / 2));
  }
  return 0;
}
