#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
long long ans[maxn];
int n, q, p[maxn], c[maxn];
struct node {
  int id, l, r, u, d;
} sq[maxn];
int lowbit(int x) { return x & (-x); }
void add(int x, int val) {
  while (x <= n) {
    c[x] += val;
    x += lowbit(x);
  }
}
int sum(int x) {
  long long ret = 0;
  while (x) {
    ret += c[x];
    x -= lowbit(x);
  }
  return ret;
}
bool cmp1(const node& a, const node& b) { return a.l < b.l; }
bool cmp2(const node& a, const node& b) { return a.r > b.r; }
bool cmp3(const node& a, const node& b) { return a.id < b.id; }
long long C2(long long n) { return n * (n - 1) / 2; }
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d %d %d %d", &sq[i].l, &sq[i].d, &sq[i].r, &sq[i].u);
    sq[i].id = i;
  }
  sort(sq + 1, sq + 1 + q, cmp1);
  int j = 1;
  for (int i = 1; i <= q; i++) {
    for (; j < sq[i].l; j++) {
      add(p[j], 1);
    }
    long long temp1 = sum(sq[i].d - 1), temp2 = sum(n) - sum(sq[i].u);
    ans[sq[i].id] = ans[sq[i].id] - C2(temp1) - C2(temp2);
  }
  memset(c, 0, sizeof(c));
  sort(sq + 1, sq + 1 + q, cmp2);
  j = n;
  for (int i = 1; i <= q; i++) {
    for (; j > sq[i].r; --j) {
      add(p[j], 1);
    }
    long long temp1 = sum(sq[i].d - 1), temp2 = sum(n) - sum(sq[i].u);
    ans[sq[i].id] = ans[sq[i].id] - C2(temp1) - C2(temp2);
  }
  sort(sq + 1, sq + 1 + q, cmp3);
  long long tot = (long long)n * (long long)(n - 1) / 2;
  for (int i = 1; i <= q; i++) {
    ans[i] = ans[i] + C2(sq[i].l - 1) + C2(n - sq[i].r) + C2(sq[i].d - 1) +
             C2(n - sq[i].u);
    printf("%lld\n", tot - ans[i]);
  }
  return 0;
}
