#include <bits/stdc++.h>
using namespace std;
int n, m, a[800001], w[800001], q[800001][4], f[800001];
struct node {
  int x, y, z, type, pos;
  bool operator<(const node &A) const { return x < A.x; }
} c[2000001];
inline void add(int x, int y) {
  for (; x <= n; x += x & (-x)) f[x] += y;
}
int calc(int x) {
  int will = 0;
  for (; x; x -= x & (-x)) will += f[x];
  return will;
}
long long C(long long n) { return n * (n - 1) / 2; }
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  int cnt = 0, num = 0;
  for (int i = 1; i <= m; i++) {
    int xx1, yy1, xx2, yy2;
    scanf("%d%d%d%d", &xx1, &yy1, &xx2, &yy2);
    q[i][0] = xx1;
    q[i][1] = yy1;
    q[i][2] = xx2;
    q[i][3] = yy2;
    c[++cnt].x = xx1 - 1;
    c[cnt].y = 1;
    c[cnt].z = yy1 - 1;
    c[cnt].type = 0;
    c[cnt].pos = ++num;
    c[++cnt].x = xx1 - 1;
    c[cnt].y = yy2 + 1;
    c[cnt].z = n;
    c[cnt].type = 0;
    c[cnt].pos = ++num;
    c[++cnt].x = xx2;
    c[cnt].y = 1;
    c[cnt].z = yy1 - 1;
    c[cnt].type = 1;
    c[cnt].pos = ++num;
    c[++cnt].x = n;
    c[cnt].y = 1;
    c[cnt].z = yy1 - 1;
    c[cnt].type = 0;
    c[cnt].pos = num;
    c[++cnt].x = xx2;
    c[cnt].y = yy2 + 1;
    c[cnt].z = n;
    c[cnt].type = 1;
    c[cnt].pos = ++num;
    c[++cnt].x = n;
    c[cnt].y = yy2 + 1;
    c[cnt].z = n;
    c[cnt].type = 0;
    c[cnt].pos = num;
  }
  sort(c + 1, c + cnt + 1);
  int Left = 1;
  for (; Left <= cnt && c[Left].x == 0; ++Left)
    ;
  for (int i = 1; i <= n; i++) {
    add(a[i], 1);
    for (; Left <= cnt && c[Left].x == i; ++Left)
      if (c[Left].type)
        w[c[Left].pos] -= calc(c[Left].z) - calc(c[Left].y - 1);
      else
        w[c[Left].pos] += calc(c[Left].z) - calc(c[Left].y - 1);
  }
  for (int i = 1; i <= m; i++) {
    long long ans = C(n);
    ans -= C(q[i][0] - 1);
    ans -= C(n - q[i][2]);
    ans -= C(q[i][1] - 1);
    ans -= C(n - q[i][3]);
    for (int j = (i - 1) * 4 + 1; j <= i * 4; j++) ans += C(w[j]);
    printf("%I64d\n", ans);
  }
}
