#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long m) {
  long long x = 1 % m;
  a %= m;
  while (b) {
    if ((1 & b)) x = x * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return x;
}
int global = 1;
struct node {
  int l, r;
  int val;
  node() { l = r = val = 0; }
} pst[4000000];
int root[200005];
int ind;
void update(int prev, int i, int j, int current) {
  pst[current] = pst[prev];
  pst[current].val += 1;
  if (i == j) return;
  int m = (i + j) >> 1;
  if (ind <= m) {
    pst[current].l = ++global;
    update(pst[prev].l, i, m, pst[current].l);
  } else {
    pst[current].r = ++global;
    update(pst[prev].r, m + 1, j, pst[current].r);
  }
}
int query(int i, int j, const int &ri, const int &rj, int root1, int root2) {
  if (ri > rj || root1 >= root2) return 0;
  if (ri <= i && j <= rj) return pst[root2].val - pst[root1].val;
  int m = (i + j) >> 1;
  int l = 0, r = 0;
  if (ri <= m) l = query(i, m, ri, rj, pst[root1].l, pst[root2].l);
  if (rj > m) r = query(m + 1, j, ri, rj, pst[root1].r, pst[root2].r);
  return l + r;
}
int main() {
  int n, q;
  scanf("%d", &n);
  scanf("%d", &q);
  memset(root, 0, sizeof(root));
  root[0] = global;
  int prev = root[0];
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    ind = x;
    root[i] = ++global;
    update(prev, 1, n, root[i]);
    prev = root[i];
  }
  while (q--) {
    int l, d, r, u;
    scanf("%d", &l);
    scanf("%d", &d);
    scanf("%d", &r);
    scanf("%d", &u);
    swap(u, d);
    pair<int, int> x[9], y[9];
    for (int i = 0; i < 3; i++) y[i] = make_pair(d + 1, n);
    for (int i = 4; i < 7; i++) y[i] = make_pair(1, u - 1);
    y[7] = y[8] = y[3] = make_pair(u, d);
    x[0] = x[7] = x[6] = make_pair(1, l - 1);
    x[1] = x[8] = x[5] = make_pair(l, r);
    for (int i = 2; i < 5; i++) x[i] = make_pair(r + 1, n);
    long long num[9];
    for (int i = 0; i < 9; i++)
      num[i] = query(1, n, y[i].first, y[i].second, root[x[i].first - 1],
                     root[x[i].second]);
    long long ans = num[0] * (num[3] + num[4] + num[5] + num[8]);
    ans += num[1] * (num[3] + num[4] + num[5] + num[6] + num[7] + num[8]);
    ans += num[2] * (num[5] + num[6] + num[7] + num[8]);
    ans += num[3] * (num[5] + num[6] + num[7] + num[8]);
    ans += num[4] * (num[7] + num[8]);
    ans += num[5] * (num[7] + num[8]);
    ans += num[6] * (num[8]);
    ans += num[7] * (num[8]);
    ans += (num[8] * (num[8] - 1)) / 2;
    printf("%lld\n", ans);
  }
}
