#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, Q, x[N], y[N];
long long c2(int n) { return 1ll * n * (n - 1) / 2; }
struct Query {
  int l, d, r, u;
  long long ans;
  void read() {
    scanf("%d%d%d%d", &l, &d, &r, &u);
    ans = c2(n) - c2(l - 1) - c2(d - 1) - c2(n - r) - c2(n - u);
  }
  void rot() {}
} q[N];
template <class T>
struct Fenwick {
  int n;
  T a[N];
  void ini(int _n) { fill_n(a + 1, n = _n, 0); }
  void add(int x, T d) {
    for (; x <= n; x += ((x) & -(x))) a[x] += d;
  }
  T sum(int x) {
    T r = 0;
    for (; x >= 1; x ^= ((x) & -(x))) r += a[x];
    return r;
  }
};
Fenwick<int> fen;
vector<pair<int, int> > ask[N];
int a[N];
int main() {
  scanf("%d%d", &n, &Q);
  for (int i = 1; i < (n + 1); ++i) scanf("%d", y + i), x[i] = i;
  for (int i = 0; i < (Q); ++i) q[i].read();
  for (int i = 0; i < (4); ++i) {
    for (int i = 1; i < (n + 1); ++i) {
      swap(x[i], y[i]);
      x[i] = n + 1 - x[i];
      a[x[i]] = y[i];
      ask[i].clear();
    }
    for (int i = 0; i < (Q); ++i) {
      int l = q[i].l, r = q[i].r, d = q[i].d, u = q[i].u;
      q[i].l = n + 1 - u, q[i].d = l;
      q[i].r = n + 1 - d, q[i].u = r;
      ask[q[i].l].push_back({q[i].d, i});
    }
    fen.ini(n);
    for (int i = 1; i < (n + 1); ++i) {
      for (auto e : ask[i]) q[e.second].ans += c2(fen.sum(e.first - 1));
      fen.add(a[i], 1);
    }
  }
  for (int i = 0; i < (Q); ++i) printf("%lld\n", q[i].ans);
  return 0;
}
