#include <bits/stdc++.h>
using namespace std;
struct NODE {
  int u, d, l, r, ind;
};
const int N = 2000 * 100 + 100;
NODE e[N];
long long ans[N], tr[2][N * 4];
int p[N], tmp[N], n;
bool comp1(NODE a, NODE b) { return (a.u < b.u); }
bool comp2(NODE a, NODE b) { return (a.d > b.d); }
void add(bool f, int l, int r, int b = 0, int e = n, int ind = 1) {
  if (l <= b && e <= r) {
    tr[f][ind]++;
    return;
  }
  int mid = (b + e) / 2;
  if (l < mid) add(f, l, r, b, mid, ind * 2);
  if (r > mid) add(f, l, r, mid, e, ind * 2 + 1);
}
long long get(bool f, int p, int b = 0, int e = n, int ind = 1) {
  long long ret = tr[f][ind];
  if (b + 1 == e) return ret;
  int mid = (b + e) / 2;
  if (p < mid)
    ret += get(f, p, b, mid, ind * 2);
  else
    ret += get(f, p, mid, e, ind * 2 + 1);
  return ret;
}
void fadd(int i) {
  add(0, p[i], n);
  add(1, 0, p[i] + 1);
  return;
}
long long f(long long k) { return k * (k - 1) / 2; }
void fget(int pt) {
  if (e[pt].l) ans[e[pt].ind] += f(get(0, e[pt].l - 1));
  if (e[pt].r + 1 != n) ans[e[pt].ind] += f(get(1, e[pt].r + 1));
  return;
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) cin >> p[i], tmp[p[i] - 1] = i;
  for (int i = 0; i < n; i++) p[i] = tmp[i];
  for (int i = 0; i < q; i++) {
    cin >> e[i].l >> e[i].u >> e[i].r >> e[i].d;
    e[i].l--, e[i].r--, e[i].u--, e[i].d--;
    e[i].ind = i;
  }
  sort(e, e + q, comp1);
  int pt = 0;
  for (int i = 0; i < n; i++) {
    fadd(i);
    while (pt < q && e[pt].u - 1 <= i) {
      if (e[pt].u - 1 == i) fget(pt);
      pt++;
    }
  }
  sort(e, e + q, comp2);
  pt = 0;
  for (int i = 0; i < 4 * n; i++) tr[0][i] = tr[1][i] = 0;
  for (int i = n - 1; i >= 0; i--) {
    fadd(i);
    while (pt < q && e[pt].d + 1 >= i) {
      if (e[pt].d + 1 == i) fget(pt);
      pt++;
    }
  }
  for (int i = 0; i < q; i++)
    ans[e[i].ind] = f(n) - f(e[i].l) - f(e[i].u) - f(n - e[i].d - 1) -
                    f(n - e[i].r - 1) + ans[e[i].ind];
  for (int i = 0; i < q; i++) cout << ans[i] << endl;
  return 0;
}
