#include <bits/stdc++.h>
const int N = 2e5 + 10;
using namespace std;
int n, q;
int num[N][9];
struct node {
  int x, y, pos;
} Q[N * 9];
int bit[1 << 20];
pair<int, int> P[N];
long long X[N], Y[N];
bool cmp(node a, node b) { return a.x < b.x; }
long long codeX(int x, int y) { return 1LL * x * n + y; }
long long codeY(int x, int y) { return 1LL * y * n + x; }
inline long long C2(int x) { return 1LL * x * (x - 1) / 2; }
void add(int x) {
  while (x <= n) {
    ++bit[x];
    x += (x & -x);
  }
}
int query(int x) {
  int res = 0;
  while (x) {
    res += bit[x];
    x -= (x & -x);
  }
  return res;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1, x; i <= n; ++i) {
    scanf("%d", &x);
    P[i - 1] = pair<int, int>(i, x);
  }
  for (int i = 0, l, d, r, u, j = 0, k; i < q; i++) {
    k = i * 9;
    scanf("%d%d%d%d", &l, &d, &r, &u);
    --l;
    --d;
    Q[j++] = node{l, d, k};
    Q[j++] = node{r, d, k + 1};
    Q[j++] = node{l, u, k + 3};
    Q[j++] = node{r, u, k + 4};
    num[i][6] = l;
    num[i][7] = r;
    num[i][2] = d;
    num[i][5] = u;
    num[i][8] = n;
  }
  q <<= 2;
  sort(Q, Q + q, [](node a, node b) { return a.x < b.x; });
  int p = 0;
  for (int i = 0; i < q; ++i) {
    while (p < n && P[p].first <= Q[i].x) add(P[p++].second);
    num[Q[i].pos / 9][Q[i].pos % 9] = query(Q[i].y);
  }
  q >>= 2;
  long long sum = C2(n);
  for (int i = 0; i < q; ++i) {
    long long ans = sum - C2(num[i][2]) - C2(num[i][6]) -
                    C2(num[i][8] - num[i][7]) - C2(num[i][8] - num[i][5]);
    num[i][5] -= num[i][4];
    num[i][8] -= num[i][7] + num[i][5];
    ans += C2(num[i][0]) + C2(num[i][6] - num[i][3]) +
           C2(num[i][2] - num[i][1]) + C2(num[i][8]);
    printf("%I64d\n", ans);
  }
  return 0;
}
