#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
class SegmentTree {
 private:
  struct PartialCascading {
    int l;
    int r;
  };
  vector<int> *t;
  vector<PartialCascading> *pos;
  int n;
  void build(int a[], int v, int vl, int vr) {
    if (vl == vr) {
      t[v].push_back(a[vl]);
      return;
    }
    int vm = (vl + vr) / 2;
    build(a, 2 * v + 1, vl, vm);
    build(a, 2 * v + 2, vm + 1, vr);
    merge(t[2 * v + 1].begin(), t[2 * v + 1].end(), t[2 * v + 2].begin(),
          t[2 * v + 2].end(), back_inserter(t[v]));
    size_t size = t[v].size();
    pos[v].resize(size + 1);
    pos[v][0].l =
        lower_bound(t[2 * v + 1].begin(), t[2 * v + 1].end(), t[v][0]) -
        t[2 * v + 1].begin();
    pos[v][0].r =
        lower_bound(t[2 * v + 2].begin(), t[2 * v + 2].end(), t[v][0]) -
        t[2 * v + 2].begin();
    for (size_t i = 1; i < size; ++i) {
      pos[v][i].l = pos[v][i - 1].l;
      pos[v][i].r = pos[v][i - 1].r;
      while (pos[v][i].l < t[2 * v + 1].size() &&
             t[v][i] > t[2 * v + 1][pos[v][i].l])
        ++pos[v][i].l;
      while (pos[v][i].r < t[2 * v + 2].size() &&
             t[v][i] > t[2 * v + 2][pos[v][i].r])
        ++pos[v][i].r;
    }
    pos[v][size].l = t[2 * v + 1].size();
    pos[v][size].r = t[2 * v + 2].size();
  }
  int query(int v, int vl, int vr, int l, int r, int val1, int val2, int posUp,
            int posLow) {
    if (vl > r || vr < l) return 0;
    if (posUp == -1 && posLow == -1) {
      posUp = upper_bound(t[v].begin(), t[v].end(), val2) - t[v].begin();
      posLow = lower_bound(t[v].begin(), t[v].end(), val1) - t[v].begin();
    }
    if (l <= vl && r >= vr) return posUp - posLow;
    int vm = (vl + vr) / 2;
    int ql = query(2 * v + 1, vl, vm, l, r, val1, val2, pos[v][posUp].l,
                   pos[v][posLow].l);
    int qr = query(2 * v + 2, vm + 1, vr, l, r, val1, val2, pos[v][posUp].r,
                   pos[v][posLow].r);
    return ql + qr;
  }

 public:
  SegmentTree(int a[], int n) : n(n) {
    t = new vector<int>[4 * n];
    pos = new vector<PartialCascading>[4 * n];
    build(a, 0, 0, n - 1);
  }
  ~SegmentTree() {
    delete[] t;
    delete[] pos;
  }
  int query(int l, int r, int val1, int val2) {
    return query(0, 0, n - 1, l, r, val1, val2, -1, -1);
  }
};
int main() {
  int n, q;
  cin >> n >> q;
  int *a = new int[n];
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
    --a[i];
  }
  SegmentTree t(a, n);
  delete[] a;
  while (q--) {
    int x, y, x2, y2;
    scanf("%d %d %d %d", &x, &y, &x2, &y2);
    --x;
    --y;
    --x2;
    --y2;
    int cnt1 = t.query(0, x - 1, 0, y - 1);
    int cnt2 = t.query(x, x2, 0, y - 1);
    int cnt3 = t.query(x2 + 1, n - 1, 0, y - 1);
    int cnt4 = t.query(0, x - 1, y, y2);
    int cnt5 = t.query(x, x2, y, y2);
    int cnt6 = t.query(x2 + 1, n - 1, y, y2);
    int cnt7 = t.query(0, x - 1, y2 + 1, n - 1);
    int cnt8 = t.query(x, x2, y2 + 1, n - 1);
    int cnt9 = t.query(x2 + 1, n - 1, y2 + 1, n - 1);
    long long ans = 1LL * cnt1 * (cnt5 + cnt6 + cnt8 + cnt9);
    ans += 1LL * cnt2 * (cnt4 + cnt5 + cnt6 + cnt7 + cnt8 + cnt9);
    ans += 1LL * cnt3 * (cnt4 + cnt5 + cnt7 + cnt8);
    ans += 1LL * cnt4 * (cnt5 + cnt6 + cnt8 + cnt9);
    ans += 1LL * cnt5 * (cnt6 + cnt7 + cnt8 + cnt9);
    ans += 1LL * cnt6 * (cnt7 + cnt8);
    ans += 1LL * cnt5 * (cnt5 - 1) / 2;
    printf("%I64d\n", ans);
  }
  return 0;
}
