#include <bits/stdc++.h>
using namespace std;
using namespace std;
inline char gc() {
  static char buf[100000], *p1 = buf, *p2 = buf;
  if (p1 == p2) {
    p2 = (p1 = buf) + fread(buf, 1, 100000, stdin);
    if (p1 == p2) return EOF;
  }
  return *p1++;
}
inline int getint() {
  char c = gc();
  if (!~c) return EOF;
  for (; c < '0' || c > '9'; c = gc())
    ;
  int x = 0;
  for (; c >= '0' && c <= '9'; x = (x << 1) + (x << 3) + (c ^ 48), c = gc())
    ;
  return x;
}
inline void pc(char c) {
  static char buf[100000], *p1 = buf, *p2 = buf + 100000;
  if (p1 == p2) {
    fwrite(buf, 1, 100000, stdout);
    p1 = buf;
  }
  if (c)
    *(p1++) = c;
  else
    fwrite(buf, 1, p1 - buf, stdout), p1 = buf;
}
inline void putll(long long x) {
  int i = 32, a[i];
  do {
    a[--i] = x % 10 ^ 48;
    x /= 10;
  } while (x);
  while (i < 32) pc(a[i++]);
  pc('\n');
}
struct fenwik_tree {
  int sum[200200];
  void init() { memset(sum, 0, sizeof sum); }
  void add(int x) {
    while (x < 200200) {
      sum[x]++, x += x & -x;
    }
  }
  int calc(int x) {
    int rlt = 0;
    while (x) {
      rlt += sum[x], x -= x & -x;
    }
    return rlt;
  }
} T;
int n, q, l[200200], r[200200], d[200200], u[200200];
int a[200200], x[200200 << 2], y[200200 << 2], ans[200200 << 2],
    id[200200 << 2];
bool cmp(int i, int j) { return x[i] < x[j]; }
long long func(int x) { return 1ll * x * (x - 1) / 2; }
int main() {
  n = getint(), q = getint();
  for (int i = 1; i <= n; i++) a[i] = getint();
  int cnt = 0;
  for (int i = 1; i <= q; i++) {
    l[i] = getint(), d[i] = getint(), r[i] = getint(), u[i] = getint();
    cnt++;
    x[cnt] = l[i] - 1, y[cnt] = d[i] - 1;
    cnt++;
    x[cnt] = l[i] - 1, y[cnt] = u[i];
    cnt++;
    x[cnt] = r[i], y[cnt] = d[i] - 1;
    cnt++;
    x[cnt] = r[i], y[cnt] = u[i];
  }
  for (int i = 1; i <= cnt; i++) id[i] = i;
  sort(id + 1, id + cnt + 1, cmp);
  T.init();
  for (int i = 1, cur = 1; i <= n && cur <= cnt; i++) {
    T.add(a[i]);
    while (cur <= cnt && x[id[cur]] <= i)
      ans[id[cur]] = T.calc(y[id[cur]]), cur++;
  }
  for (int i = 1; i <= cnt; i++)
    if (!x[i] || !y[i]) ans[i] = 0;
  int lu, lm, ld, mu, mm, md, ru, rm, rd;
  long long all = func(n), rlt;
  for (int i = 1; i <= q; i++) {
    ld = ans[(i - 1) * 4 + 1];
    lm = ans[(i - 1) * 4 + 2] - ld;
    lu = l[i] - 1 - ld - lm;
    md = ans[(i - 1) * 4 + 3] - ld;
    mm = ans[(i - 1) * 4 + 4] - ld - lm - md;
    mu = r[i] - l[i] + 1 - md - mm;
    rd = d[i] - 1 - ld - md;
    rm = u[i] - d[i] + 1 - lm - mm;
    ru = n - r[i] - rd - rm;
    rlt = all - func(lu + mu + ru) - func(lu + lm + ld) - func(ld + md + rd) -
          func(rd + rm + ru) + func(lu) + func(ld) + func(rd) + func(ru);
    putll(rlt);
  }
  pc(0);
  return 0;
}
