#include <bits/stdc++.h>
using namespace std;
struct node {
  int x, y, z, t;
  node() {}
  node(int x, int y, int z, int t) : x(x), y(y), z(z), t(t){};
  bool operator<(const node &a) const { return x < a.x; }
} a[410000 << 2];
long long ans[410000];
long long ct(int a) { return 1ll * a * (a - 1) / 2; }
int n, f[410000], b[410000], m, cnt;
void add(int x) {
  for (; x <= n; x += x & -x) b[x]++;
}
int ask(int x) {
  int tmp = 0;
  for (; x; x -= x & -x) tmp += b[x];
  return tmp;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &f[i]);
  for (int i = 1; i <= m; i++) {
    int l, d, r, u;
    scanf("%d%d%d%d", &l, &d, &r, &u);
    ans[i] = (long long)ct(l - 1) + ct(d - 1) + ct(n - r) + ct(n - u);
    a[++cnt] = node(l, d, 0, i);
    a[++cnt] = node(l, u, 1, i);
    a[++cnt] = node(r, d, 2, i);
    a[++cnt] = node(r, u, 3, i);
  }
  sort(a + 1, a + cnt + 1);
  memset(b, 0, sizeof(b));
  for (int i = 1, j = 1; i <= n; i++) {
    for (; a[j].x == i; j++)
      if (a[j].z == 0)
        ans[a[j].t] -= ct(ask(a[j].y - 1));
      else if (a[j].z == 1)
        ans[a[j].t] -= ct(i - 1 - ask(a[j].y));
    add(f[i]);
  }
  memset(b, 0, sizeof(b));
  for (int i = n, j = cnt; i; i--) {
    for (; a[j].x == i; j--)
      if (a[j].z == 2)
        ans[a[j].t] -= ct(ask(a[j].y - 1));
      else if (a[j].z == 3)
        ans[a[j].t] -= ct(n - i - ask(a[j].y));
    add(f[i]);
  }
  for (int i = 1; i <= m; i++) printf("%I64d\n", ct(n) - ans[i]);
  return 0;
}
