#include <bits/stdc++.h>
struct query {
  int l, d, r, u;
  int ind;
  long long s;
};
using namespace std;
long long n, q;
pair<int, int> a[200005];
long long dp[200005][4];
int p;
query g[200005];
int bit[200005];
bool sbu(query x, query y) { return x.u < y.u; }
bool sbl(query x, query y) { return x.l < y.l; }
bool sbd(query x, query y) { return x.d > y.d; }
bool sbr(query x, query y) { return x.r > y.r; }
bool sbi(query x, query y) { return x.ind < y.ind; }
void dodaj(int x) {
  while (x <= 200000) {
    bit[x]++;
    x = x + (x & (-x));
  }
}
int vrati(int x) {
  if (x <= 0) return 0;
  int s = 0;
  while (x > 0) {
    s += bit[x];
    x = x - (x & (-x));
  }
  return s;
}
void resetuj() {
  for (int i = 0; i <= 200000; i++) bit[i] = 0;
}
int main() {
  scanf("%lld %d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &p);
    a[i] = make_pair(n - p, i);
  }
  for (int i = 0; i < q; i++) {
    scanf("%d %d %d %d", &g[i].l, &g[i].d, &g[i].r, &g[i].u);
    g[i].ind = i;
    g[i].l--;
    g[i].d = n - g[i].d;
    g[i].r--;
    g[i].u = n - g[i].u;
    g[i].l--;
    g[i].r++;
    g[i].d++;
    g[i].u--;
    g[i].s = (n * (n - 1)) / 2;
  }
  sort(a, a + n);
  sort(g, g + q, sbu);
  long long k = 0;
  int l = 0;
  long long c;
  long long f;
  while (l < q && g[l].u == -1) l++;
  for (int i = 0; i < n; i++) {
    while (k < n && a[k].first == i) {
      dodaj(a[k].second + 1);
      k++;
    }
    while (l < q && g[l].u == i) {
      c = vrati(g[l].l + 1);
      g[l].s += (c * (c - 1)) / 2;
      c = vrati(g[l].r);
      c = k - c;
      g[l].s += (c * (c - 1)) / 2;
      l++;
    }
    dp[i][0] = (k * (k - 1)) / 2;
  }
  k = 0;
  resetuj();
  sort(g, g + q, sbd);
  l = 0;
  while (l < q && g[l].d == n) l++;
  for (int i = n - 1; i >= 0; i--) {
    while (k < n && a[n - k - 1].first == i) {
      dodaj(a[n - k - 1].second + 1);
      k++;
    }
    while (l < q && g[l].d == i) {
      c = vrati(g[l].l + 1);
      g[l].s += (c * (c - 1)) / 2;
      c = vrati(g[l].r);
      c = k - c;
      g[l].s += (c * (c - 1)) / 2;
      l++;
    }
    dp[i][1] = (k * (k - 1)) / 2;
  }
  for (int i = 0; i < n; i++) {
    p = a[i].first;
    a[i].first = a[i].second;
    a[i].second = p;
  }
  sort(a, a + n);
  k = 0;
  for (int i = 0; i < n; i++) {
    dp[i][2] = ((n - k) * (n - k - 1)) / 2;
    while (k < n && a[k].first == i) k++;
    dp[i][3] = (k * (k - 1)) / 2;
  }
  sort(g, g + q, sbi);
  for (int i = 0; i < q; i++) {
    if (g[i].d != n) g[i].s -= dp[g[i].d][1];
    if (g[i].u != -1) g[i].s -= dp[g[i].u][0];
    if (g[i].r != n) g[i].s -= dp[g[i].r][2];
    if (g[i].l != -1) g[i].s -= dp[g[i].l][3];
    printf("%lld\n", g[i].s);
  }
  return 0;
}
