#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n, q, p[N];
vector<int> save[2 * N];
void init() {
  for (int i = 0; i < n; ++i) save[i + n].emplace_back(p[i]);
  for (int i = n - 1; i >= 1; --i) {
    int p1 = 0, p2 = 0;
    while (p1 < save[2 * i].size() && p2 < save[2 * i + 1].size()) {
      if (save[2 * i][p1] < save[2 * i + 1][p2])
        save[i].emplace_back(save[2 * i][p1++]);
      else
        save[i].emplace_back(save[2 * i + 1][p2++]);
    }
    while (p1 < save[2 * i].size()) save[i].emplace_back(save[2 * i][p1++]);
    while (p2 < save[2 * i + 1].size())
      save[i].emplace_back(save[2 * i + 1][p2++]);
  }
}
int query(int l, int r, int x) {
  int ans = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1)
      ans += lower_bound(begin(save[l]), end(save[l]), x) - begin(save[l]), ++l;
    if (r & 1)
      --r, ans += lower_bound(begin(save[r]), end(save[r]), x) - begin(save[r]);
  }
  return ans;
}
int sum(int x1, int y1, int x2, int y2) {
  if (x1 > x2 || y1 > y2) return 0;
  return query(x1 - 1, x2, y2) - query(x1 - 1, x2, y1 - 1);
}
long long asc(int x) { return 1LL * x * (x - 1) / 2; }
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 0; i < n; ++i) cin >> p[i], --p[i];
  init();
  int a1, a2, a3, a4, c1, c2, c3, c4, x1, y1, x2, y2;
  long long r1, r2;
  for (int i = 0; i < q; ++i) {
    cin >> x1 >> y1 >> x2 >> y2;
    --x1, --y1, ++x2, ++y2;
    a1 = sum(1, 1, x1, n), a2 = sum(x2, 1, n, n);
    a3 = sum(1, 1, n, y1), a4 = sum(1, y2, n, n);
    r1 = asc(a1) + asc(a2) + asc(a3) + asc(a4);
    c1 = sum(1, y2, x1, n), c2 = sum(x2, y2, n, n);
    c3 = sum(1, 1, x1, y1), c4 = sum(x2, 1, n, y1);
    r2 = asc(c1) + asc(c2) + asc(c3) + asc(c4);
    cout << asc(n) - r1 + r2 << "\n";
  }
}
