#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long long MAX = 1 << 18;
long long t[2 * MAX], ans[MAX], tab[MAX];
pair<long long, long long> y[MAX];
bool O[MAX];
priority_queue<pair<long long, long long> > Q;
long long func(long long i) { return i * (i - 1) / 2; }
void update(long long u) {
  for (t[u += MAX]++; u > 1; u >>= 1) t[u >> 1] = t[u] + t[u ^ 1];
}
long long query(long long u, long long v) {
  long long sum = 0;
  for (u += MAX, v += MAX + 1; u < v; u >>= 1, v >>= 1) {
    if (u & 1) sum += t[u++];
    if (v & 1) sum += t[--v];
  }
  return sum;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n, q;
  cin >> n >> q;
  for (long long i = 1; i <= n; i++) cin >> tab[i], Q.push(make_pair(-i, -1));
  for (long long i = 1; i <= q; i++) {
    long long l, d, r, u;
    cin >> l >> d >> r >> u;
    y[i] = make_pair(d, u);
    ans[i] = func(l - 1) + func(d - 1) + func(n - r) + func(n - u);
    Q.push(make_pair(-l, i)), Q.push(make_pair(-(r + 1), i));
  }
  while (!Q.empty()) {
    long long nr = Q.top().second, num = Q.top().first;
    Q.pop();
    if (nr < 0) {
      update(tab[-num]);
      continue;
    }
    if (O[nr])
      ans[nr] -= func(y[nr].first - 1 - query(1, y[nr].first - 1)) +
                 func(n - y[nr].second - query(y[nr].second + 1, n));
    else
      O[nr] = true, ans[nr] -= func(query(1, y[nr].first - 1)) +
                               func(query(y[nr].second + 1, n));
  }
  for (long long i = 1; i <= q; i++) cout << func(n) - ans[i] << "\n";
  return 0;
}
