#include <bits/stdc++.h>
using namespace std;
int n, m, a[1000009], c[1000009];
long long ans[1000009];
struct node {
  int x1, x2, y1, y2, id;
} q[1000009];
bool cmp1(node u, node v) { return u.x1 < v.x1; }
bool cmp2(node u, node v) { return u.x2 > v.x2; }
void ins(int x, int y) {
  for (; x <= n; x += x & -x) c[x] += y;
}
int qry(int x) {
  int y = 0;
  for (; x; x ^= x & -x) y += c[x];
  return y;
}
long long calc(int x) { return (long long)x * (x - 1) >> 1; }
int main() {
  scanf("%d%d", &n, &m);
  int i, j;
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i <= m; i++) {
    scanf("%d%d%d%d", &q[i].x1, &q[i].y1, &q[i].x2, &q[i].y2);
    q[i].id = i;
    ans[i] = calc(q[i].x1 - 1) + calc(n - q[i].x2);
    ans[i] += calc(q[i].y1 - 1) + calc(n - q[i].y2);
  }
  sort(q + 1, q + m + 1, cmp1);
  for (i = j = 1; i <= n; i++) {
    for (; j <= m && q[j].x1 == i; j++) {
      ans[q[j].id] -= calc(qry(q[j].y1 - 1)) + calc(i - 1 - qry(q[j].y2));
    }
    ins(a[i], 1);
  }
  memset(c, 0, sizeof(c));
  sort(q + 1, q + m + 1, cmp2);
  for (i = n, j = 1; i; i--) {
    for (; j <= m && q[j].x2 == i; j++) {
      ans[q[j].id] -= calc(qry(q[j].y1 - 1)) + calc(n - i - qry(q[j].y2));
    }
    ins(a[i], 1);
  }
  for (i = 1; i <= m; i++)
    printf("%lld\n", (long long)n * (n - 1) / 2 - ans[i]);
  return 0;
}
