#include <bits/stdc++.h>
using namespace std;
struct BIT {
  int s[262145];
  void add(int x) {
    while (x < 262144) {
      s[x]++;
      x += (x & (-x));
    }
  }
  int query(int x) {
    int ret = 0;
    while (x) {
      ret += s[x];
      x -= (x & (-x));
    }
    return ret;
  }
} bit;
struct Q {
  int x, y1, y2, t, id;
  Q(int xi, int y1i, int y2i, int ti, int idi) {
    x = xi;
    y1 = y1i;
    y2 = y2i;
    t = ti;
    id = idi;
  }
  Q() {}
};
bool comp(Q A, Q B) { return A.x < B.x; }
vector<Q> q;
int a[262145];
long long ans[262145][9];
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < m; ++i) {
    int x1, x2, y1, y2;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    q.push_back(Q(x1, y1 - 1, y2, 0, i));
    q.push_back(Q(x2 + 1, y1 - 1, y2, 1, i));
    q.push_back(Q(n + 1, y1 - 1, y2, 2, i));
  }
  int nowx = 1;
  sort(q.begin(), q.end(), comp);
  for (int i = 0; i < int(q.size()); ++i) {
    while (nowx < q[i].x) {
      bit.add(a[nowx]);
      nowx++;
    }
    ans[q[i].id][q[i].t * 3] = bit.query(q[i].y1);
    ans[q[i].id][q[i].t * 3 + 1] = bit.query(q[i].y2);
    ans[q[i].id][q[i].t * 3 + 2] = bit.query(n);
  }
  for (int i = 0; i < m; ++i) {
    for (int k = 0; k < 9; ++k) {
      for (int j = 0; j < k; ++j) {
        if (k % 3 >= j % 3) ans[i][k] -= ans[i][j];
      }
    }
    long long fans = 0;
    fans += (ans[i][0] + ans[i][3]) *
            (ans[i][4] + ans[i][5] + ans[i][7] + ans[i][8]);
    fans += ans[i][1] * (ans[i][3] + ans[i][4] + ans[i][5] + ans[i][6] +
                         ans[i][7] + ans[i][8]);
    fans += ans[i][2] * (ans[i][3] + ans[i][4] + ans[i][6] + ans[i][7]);
    if (ans[i][4]) fans += (ans[i][4] * (ans[i][4] - 1)) / 2;
    fans += ans[i][4] * (ans[i][5] + ans[i][6] + ans[i][7] + ans[i][8]);
    fans += ans[i][5] * (ans[i][6] + ans[i][7]);
    printf("%lld\n", fans);
  }
  return 0;
}
