#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const long long inf = 1e12;
int t[N];
int n, q;
void upd(int pos, int val) {
  for (; pos < n; pos |= (pos + 1)) {
    t[pos] += val;
  }
}
int get(int r) {
  int ans = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) {
    ans += t[r];
  }
  return ans;
}
int get(int l, int r) { return get(r) - get(l - 1); }
long long calc(long long val) { return val * (val - 1) / 2; }
int a[N];
vector<pair<pair<int, int>, pair<int, int> > > v[N];
vector<int> num[N];
void put(int l, int r, int d, int u, int i, int c) {
  if ((l > r) || (d > u)) return;
  if (l) {
    v[l - 1].push_back({{d, u}, {i, -1}});
    num[l - 1].push_back(c);
  }
  v[r].push_back({{d, u}, {i, 1}});
  num[r].push_back(c);
}
void put1(int l, int r, int d, int u, int i) {
  put(0, l - 1, 0, n - 1, i, 0);
  put(r + 1, n - 1, 0, n - 1, i, 1);
  put(0, n - 1, 0, d - 1, i, 2);
  put(0, n - 1, u + 1, n - 1, i, 3);
  put(0, l - 1, 0, d - 1, i, 4);
  put(0, l - 1, u + 1, n - 1, i, 5);
  put(r + 1, n - 1, 0, d - 1, i, 6);
  put(r + 1, n - 1, u + 1, n - 1, i, 7);
}
long long ans[N][8];
long long an[N];
int main() {
  cin >> n >> q;
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    a[i]--;
  }
  for (int i = 0; i < q; ++i) {
    an[i] += calc(n);
    int l, d, r, u;
    scanf("%d %d %d %d", &l, &d, &r, &u);
    l--;
    r--;
    d--;
    u--;
    put1(l, r, d, u, i);
  }
  for (int i = 0; i < n; ++i) {
    upd(a[i], 1);
    for (int j = 0; j < v[i].size(); ++j) {
      auto it = v[i][j];
      auto f = it.first;
      auto s = it.second;
      ans[s.first][num[i][j]] += get(f.first, f.second) * s.second;
    }
  }
  for (int i = 0; i < q; ++i) {
    for (int j = 0; j < 4; ++j) {
      an[i] -= calc(ans[i][j]);
    }
    for (int j = 4; j < 8; ++j) {
      an[i] += calc(ans[i][j]);
    }
    cout << an[i] << endl;
  }
  return 0;
}
