#include <bits/stdc++.h>
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  char ch;
  while (blank(ch = nc()))
    ;
  if (IOerror) return;
  for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
    ;
}
};  // namespace fastIO
template <class T>
inline T lowbit(T x) {
  return x & (-x);
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline bool scan(T &ret) {
  char c;
  int sgn;
  if (c = getchar(), c == EOF) return 0;
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  sgn = (c == '-') ? -1 : 1;
  ret = (c == '-') ? 0 : (c - '0');
  while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
  ret *= sgn;
  return 1;
}
const double pi = 3.14159265358979323846264338327950288L;
using namespace std;
int c[200005];
vector<pair<pair<int, int>, pair<int, int> > > a;
struct node {
  pair<int, int> x, y;
  int id;
  node(pair<int, int> a, pair<int, int> b, int _) { x = a, y = b, id = _; }
  bool operator<(const node &a) const { return y < a.y; }
};
vector<node> b;
map<pair<int, int>, int> gg;
int n, q, p[200005];
void add(int x) {
  for (int i = x; i < 200005; i += lowbit(i)) c[i]++;
}
int sum(int x) {
  if (x <= 0) return 0;
  int ans = 0;
  for (int i = x; i > 0; i -= lowbit(i)) ans += c[i];
  return ans;
}
long long f(long long x) { return x * (x - 1) / 2; }
void solve() {
  int sz = b.size();
  sort(b.begin(), b.end());
  int l = 0;
  while (b[l].y.first == 0 && l + 1 < sz) l++;
  for (int i = 1; i <= n; i++) {
    add(p[i]);
    while (l < sz && b[l].y.first == i) {
      int tmp = sum(b[l].y.second);
      gg[b[l].y] = tmp;
      l++;
    }
  }
  for (int i = 0; i < q; i++) {
    long long k1, k2, k3, k4, k5, k6, k7, k8, k9;
    int x1 = a[i].first.first, x2 = a[i].second.first, yzzz = a[i].first.second,
        y2 = a[i].second.second;
    k1 = gg[make_pair(x1 - 1, yzzz - 1)];
    k2 = gg[make_pair(x1 - 1, y2)] - k1;
    k3 = gg[make_pair(x1 - 1, n)] - k1 - k2;
    k4 = gg[make_pair(x2, yzzz - 1)] - k1;
    k5 = gg[make_pair(x2, y2)] - k4 - k2 - k1;
    k6 = gg[make_pair(x2, n)] - k1 - k2 - k3 - k4 - k5;
    k7 = gg[make_pair(n, yzzz - 1)] - k1 - k4;
    k8 = gg[make_pair(n, y2)] - k1 - k2 - k4 - k5 - k7;
    k9 = gg[make_pair(n, n)] - k1 - k2 - k3 - k4 - k5 - k6 - k7 - k8;
    long long ans =
        f(k1) + f(k2) + f(k3) + f(k4) + f(k6) + f(k7) + f(k8) + f(k9);
    ans += k1 * k2 + k2 * k3 + k1 * k3 + k1 * k4 + k1 * k7 + k4 * k7 + k7 * k8 +
           k7 * k9 + k8 * k9 + k3 * k6 + k3 * k9 + k6 * k9;
    printf("%lld\n", 1LL * n * (n - 1) / 2 - ans);
  }
}
int main() {
  cin >> n >> q;
  gg.clear();
  a.clear();
  b.clear();
  memset(c, 0, sizeof(c));
  for (int i = 1; i <= n; i++) scan(p[i]);
  for (int i = 0; i < q; i++) {
    int x1, x2, yzzz, y2;
    scanf("%d%d%d%d", &x1, &yzzz, &x2, &y2);
    if (x1 > x2) swap(x1, x2);
    if (yzzz > y2) swap(yzzz, y2);
    a.push_back(make_pair(make_pair(x1, yzzz), make_pair(x2, y2)));
    b.push_back(node(make_pair(1, 1), make_pair(x1 - 1, yzzz - 1), 1));
    b.push_back(node(make_pair(1, yzzz), make_pair(x1 - 1, y2), 2));
    b.push_back(node(make_pair(1, y2 + 1), make_pair(x1 - 1, n), 3));
    b.push_back(node(make_pair(x1, 1), make_pair(x2, yzzz - 1), 1));
    b.push_back(node(make_pair(x1, yzzz), make_pair(x2, y2), 2));
    b.push_back(node(make_pair(x1, y2 + 1), make_pair(x2, n), 3));
    b.push_back(node(make_pair(x2 + 1, 1), make_pair(n, yzzz - 1), 1));
    b.push_back(node(make_pair(x2 + 1, yzzz), make_pair(n, y2), 2));
    b.push_back(node(make_pair(x2 + 1, y2 + 1), make_pair(n, n), 3));
  }
  solve();
  return 0;
}
