#include <bits/stdc++.h>
using namespace std;
int n, m, a[1111116], f[1111116];
long long e[1111116], ans[1111116];
struct qry {
  int id, x, u, v;
} q[2][1111116];
bool cmp(qry x, qry y) { return x.x < y.x; }
void modify(int x) {
  if (x > n) return;
  f[x]++;
  modify(x + (x & -x));
}
int query(int x) {
  if (!x) return 0;
  return f[x] + query(x - (x & -x));
}
int read() {
  int x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    ;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  return x;
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; i++) a[i] = read(), e[i] = 1ll * i * (i - 1) / 2;
  for (int i = 1; i <= m; i++) {
    int x = read(), u = read(), y = read(), v = read();
    ans[i] = e[n] - e[x - 1] - e[n - y] - e[u - 1] - e[n - v];
    q[0][2 * i - 1] = (qry){i, x - 1, 1, u - 1};
    q[0][2 * i] = (qry){i, x - 1, v + 1, n};
    q[1][2 * i - 1] = (qry){i, y + 1, 1, u - 1};
    q[1][2 * i] = (qry){i, y + 1, v + 1, n};
  }
  sort(q[0] + 1, q[0] + 2 * m + 1, cmp);
  sort(q[1] + 1, q[1] + 2 * m + 1, cmp);
  for (int i = 1, j = 1; i <= n; i++) {
    modify(a[i]);
    for (; q[0][j].id && q[0][j].x <= i; j++)
      ans[q[0][j].id] += e[query(q[0][j].v) - query(q[0][j].u - 1)];
  }
  memset(f, 0, sizeof(f));
  for (int i = n, j = 2 * m; i >= 1; i--) {
    modify(a[i]);
    for (; q[1][j].id && q[1][j].x >= i; j--)
      ans[q[1][j].id] += e[query(q[1][j].v) - query(q[1][j].u - 1)];
  }
  for (int i = 1; i <= m; i++) printf("%I64d\n", ans[i]);
  return 0;
}
