#include <bits/stdc++.h>
using namespace std;
ostream &operator<<(ostream &os, const vector<int> &a) {
  os << "[";
  for (int i = 0; i < a.size(); i++) {
    os << a[i];
    if (i < a.size() - 1) os << ",";
  }
  os << "]";
  return os;
}
vector<int> sorted;
vector<int> dat[25];
vector<int> le[25], ri[25];
int n;
void build(int l, int r, int d) {
  int p = l, md = (l + r) / 2, p2 = md;
  if (l + 1 == r) return;
  for (int i = l; i < r; i++) {
    if (dat[d][i] < sorted[md])
      dat[d + 1][p++] = dat[d][i];
    else
      dat[d + 1][p2++] = dat[d][i];
    le[d][i] = p - l;
    ri[d][i] = p2 - md;
  }
  build(l, md, d + 1);
  build(md, r, d + 1);
}
void init(vector<int> v) {
  dat[0] = v;
  sorted = v;
  sort(sorted.begin(), sorted.end());
  for (int i = 0; i < 23; i++)
    dat[i + 1] = vector<int>(n + 10, 0), le[i] = vector<int>(n + 10, 0),
            ri[i] = vector<int>(n + 10, 0);
  build(0, n, 0);
}
int num(int x, int y, int d = 0, int l = 0, int r = n) {
  if (x < 0 || y < 0) return 0;
  int ret;
  if (l + 1 == r) {
    if (dat[d][l] <= y)
      ret = 1;
    else
      ret = 0;
  } else {
    int mi = (l + r) / 2;
    if (sorted[mi] <= y)
      ret = le[d][l + x] + num(x - le[d][l + x], y, d + 1, mi, r);
    else
      ret = num(le[d][l + x] - 1, y, d + 1, l, mi);
  }
  return ret;
}
long long cal[5][5], ca2[5][5];
int main() {
  vector<int> v;
  int q, a, l, d, u, r;
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a);
    a--;
    v.push_back(a);
  }
  init(v);
  for (int k = 0; k < q; k++) {
    scanf("%d %d %d %d", &l, &d, &r, &u);
    l--;
    d--;
    vector<int> ta, yo;
    ta.push_back(0);
    ta.push_back(l);
    ta.push_back(r);
    ta.push_back(n);
    yo.push_back(0);
    yo.push_back(d);
    yo.push_back(u);
    yo.push_back(n);
    for (int i = 0; i < 3; i++)
      for (int j = 0; j < 3; j++) {
        cal[i][j] = num(ta[i + 1] - 1, yo[j + 1] - 1);
        ca2[i][j] = cal[i][j];
        if (i > 0) ca2[i][j] -= cal[i - 1][j];
        if (j > 0) ca2[i][j] -= cal[i][j - 1];
        if (i > 0 && j > 0) ca2[i][j] += cal[i - 1][j - 1];
      }
    for (int i = 0; i < 3; i++) {
    }
    for (int i = 0; i < 3; i++) {
    }
    long long sum = 0;
    for (int i = 0; i < 3; i++)
      for (int j = 0; j < 3; j++)
        for (int I = 0; I < 3; I++)
          for (int J = 0; J < 3; J++) {
            if ((i - 1) * (j - 1) > 0 || (I - 1) * (J - 1) > 0) continue;
            if (i * j * I * J == 1)
              sum += ca2[i][I] * (ca2[i][I] - 1);
            else
              sum += ca2[i][I] * ca2[j][J];
          }
    printf("%I64d\n", sum / 2);
  }
}
