#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
double fRand(double fMin, double fMax) {
  double f = (double)rand() / RAND_MAX;
  return fMin + f * (fMax - fMin);
}
template <class T>
T min(T a, T b, T c) {
  return min(a, min(b, c));
}
template <class T>
T max(T a, T b, T c) {
  return max(a, max(b, c));
}
struct Node {
  int cnt;
  Node *l, *r;
  Node(int cnt, Node *l, Node *r) : cnt(cnt), l(l), r(r) {}
};
struct PersistentIT {
 private:
  vector<Node *> t;
  int n;
  Node *init(int l, int r) {
    if (l == r) return new Node(0, NULL, NULL);
    int m = (l + r) / 2;
    return new Node(0, init(l, m), init(m + 1, r));
  }
  Node *update(Node *root, int l, int r, int x) {
    if (x < l || x > r) return root;
    if (x == l && x == r) return new Node(root->cnt + 1, NULL, NULL);
    int m = (l + r) / 2;
    return new Node(root->cnt + 1, update(root->l, l, m, x),
                    update(root->r, m + 1, r, x));
  }
  int query(Node *root, int l, int r, int x, int y) {
    if (r < x || l > y) return 0;
    if (x <= l && r <= y) return root->cnt;
    int m = (l + r) / 2;
    return query(root->l, l, m, x, y) + query(root->r, m + 1, r, x, y);
  }

 public:
  PersistentIT() {}
  void init(int _n, int a[]) {
    n = _n;
    t.assign(n + 1, new Node(0, NULL, NULL));
    t[0] = init(1, n);
    for (int i = (1); i <= (n); ++i) {
      t[i] = update(t[i - 1], 1, n, a[i]);
    }
  }
  int query(int l, int r, int x, int y) {
    if (x > y) return 0;
    int t1 = query(t[r], 1, n, x, y), t2 = query(t[l - 1], 1, n, x, y);
    return t1 - t2;
  }
};
long long tri(long long x) { return x * (x - 1) / 2; }
int n, q, p[200005];
PersistentIT t;
long long Solve(int l, int r, int d, int u) {
  if (l > r) return 0;
  int k = (r - l + 1), nu = t.query(l, r, u + 1, n),
      nd = t.query(l, r, 1, d - 1);
  long long res = tri(k) - tri(nu) - tri(nd);
  return res;
}
bool isInt(int l, int r, int x, int y) {
  if (l > r) swap(l, r);
  if (x > y) swap(x, y);
  return (!(l > y && x < r));
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = (1); i <= (n); ++i) scanf("%d", &p[i]);
  t.init(n, p);
  for (int i = (1); i <= (q); ++i) {
    int l, d, r, u;
    scanf("%d%d%d%d", &l, &d, &r, &u);
    printf("%lld\n",
           Solve(1, n, d, u) - (Solve(1, l - 1, d, u) + Solve(r + 1, n, d, u)));
  }
  return 0;
}
