#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int const N = 100 * 1000 + 16;
int const M = 1000 * 1000 * 1000 + 7;
struct fenwick {
  int n;
  vector<int> a;
  fenwick(int n) {
    this->n = n;
    a.assign(n, 0);
  }
  int add(int x, int v) {
    for (int i = x; i < n; i += (i + 1) & -(i + 1)) a[i] += v;
  }
  int query(int x) {
    int sum = 0;
    for (int i = x; i >= 0; i -= (i + 1) & -(i + 1)) sum += a[i];
    return sum;
  }
};
int n, q;
int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);
  cin >> n >> q;
  vector<pii> p(n);
  for (int i = (0); i < (n); ++i) {
    p[i].first = i + 1;
    cin >> p[i].second;
  }
  vector<tuple<int, int, int>> points;
  int m = 4 * (q - 1) + 4 + 1;
  points.reserve(4 * m + 1);
  auto f = [&points](int x1, int y1, int x2, int y2, int i) {
    if (x1 > x2 && y1 > y2) return;
    points.emplace_back(x2, y2, i);
    points.emplace_back(x1 - 1, y2, -i);
    points.emplace_back(x2, y1 - 1, -i);
    points.emplace_back(x1 - 1, y1 - 1, i);
  };
  vector<tuple<int, int, int, int>> queries(q);
  for (int i = (0); i < (q); ++i) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    queries[i] = make_tuple(x1, y1, x2, y2);
    f(1, 1, x1 - 1, y1 - 1, 4 * i + 1);
    f(1, y2 + 1, x1 - 1, n, 4 * i + 2);
    f(x2 + 1, 1, n, y1 - 1, 4 * i + 3);
    f(x2 + 1, y2 + 1, n, n, 4 * i + 4);
  }
  sort(p.begin(), p.end());
  stable_sort(points.begin(), points.end());
  fenwick t(n + 1);
  vector<int> cnt(m);
  for (int i = 0, j = 0; i < points.size(); ++i) {
    int l, r, idx;
    tie(l, r, idx) = points[i];
    while (j < n && p[j].first <= l) t.add(p[j++].second, 1);
    cnt[abs(idx)] += max(-1, min(1, idx)) * t.query(r);
  }
  auto c2 = [](ll x) { return x * (x - 1) / 2; };
  ll all = c2(n);
  for (int i = (0); i < (q); ++i) {
    int l, d, r, u;
    tie(l, d, r, u) = queries[i];
    ll ans = 0;
    ans += c2(l - 1);
    ans += c2(d - 1);
    ans += c2(n - r);
    ans += c2(n - u);
    ans -= c2(cnt[4 * i + 1]);
    ans -= c2(cnt[4 * i + 2]);
    ans -= c2(cnt[4 * i + 3]);
    ans -= c2(cnt[4 * i + 4]);
    cout << all - ans << "\n";
  }
}
