#include <bits/stdc++.h>
using namespace std;
void addmod(int &a, long long b) {
  a = (a + b);
  if (a >= 1000000007) a -= 1000000007;
}
void mulmod(int &a, long long b) { a = (a * b) % 1000000007; }
template <class T>
bool domin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool domax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
int gi() {
  int a;
  scanf("%d", &a);
  return a;
}
long long gll() {
  long long a;
  scanf("%lld", &a);
  return a;
}
template <typename T>
class fenwick {
  int n;
  vector<T> a;

 public:
  fenwick(int n) : n(n), a(n + 1, 0) {}
  void reset() {
    a.clear();
    a.resize(n + 1, 0);
  }
  T getsum(int ix) {
    T ret = 0;
    for (int i = ix; i > 0; i -= (i & (-i))) ret += a[i];
    return ret;
  }
  T getsumbw(int ia, int ib) { return (getsum(ib) - getsum(ia - 1)); }
  void add(int ix, T val) {
    for (int i = ix; i <= n; i += (i & (-i))) a[i] += val;
  }
  T getval(int ix) {
    T ret = a[ix];
    if (ix > 0) {
      int tmp = ix - (ix & (-ix));
      ix--;
      while (ix != tmp) {
        ret -= a[ix];
        ix -= (ix & (-ix));
      }
    }
    return ret;
  }
};
struct node {
  long long low, high;
  int index;
  node(long long low, long long high, int index)
      : low(low), high(high), index(index) {}
};
int main() {
  long long n = gi(), q = gi();
  vector<int> ri(n + 1);
  long long mr = n * (n - 1) / 2;
  vector<long long> ans(q, mr);
  vector<vector<node>> ql(n + 1), qr(n + 1);
  for (auto i = 1; i < n + 1; i++) {
    ri[i] = gi();
  }
  for (int i = 0; i < q; i++) {
    long long l = gi(), d = gi(), r = gi(), u = gi();
    ql[l].push_back({d, u, i});
    qr[r].push_back({d, u, i});
    ans[i] -= (l - 2) * (l - 1) / 2;
    ans[i] -= (d - 2) * (d - 1) / 2;
    ans[i] -= (n - r) * (n - r - 1) / 2;
    ans[i] -= (n - u) * (n - u - 1) / 2;
  }
  fenwick<int> fw(n + 1);
  for (int ci = 1; ci <= n; ci++) {
    for (node no : ql[ci]) {
      long long nl = 0;
      if (no.low > 1) nl = fw.getsum(no.low - 1);
      long long nh = ci - 1 - fw.getsum(no.high);
      int ix = no.index;
      ans[ix] += nl * (nl - 1) / 2;
      ans[ix] += nh * (nh - 1) / 2;
    }
    fw.add(ri[ci], 1);
  }
  fw.reset();
  for (int ci = n; ci > 0; ci--) {
    for (node no : qr[ci]) {
      long long nl = 0;
      if (no.low > 1) nl = fw.getsum(no.low - 1);
      long long nh = n - ci - fw.getsum(no.high);
      int ix = no.index;
      ans[ix] += nl * (nl - 1) / 2;
      ans[ix] += nh * (nh - 1) / 2;
    }
    fw.add(ri[ci], 1);
  }
  for (int ix = 0; ix < q; ix++) {
    cout << ans[ix] << endl;
  }
  return 0;
}
