#include <bits/stdc++.h>
using namespace std;
template <typename Type = int>
struct BIT {
  int bit_size;
  vector<Type> data;
  BIT(int n) {
    bit_size = n;
    data.assign(n + 2, 0);
  }
  void add(int k, Type x) {
    k++;
    while (k <= bit_size) {
      data[k] += x;
      k += k & (-k);
    }
  }
  Type query(int k) {
    Type rec = 0;
    while (k > 0) {
      rec += data[k];
      k -= k & (-k);
    }
    return rec;
  }
  Type query(int a, int b) { return query(b) - query(a); }
};
vector<pair<int, pair<int, int>>> qs;
int l[200010], d[200010], r[200010], u[200010];
int counter[200010][3][3];
int main() {
  int N, Q, P[200010], P_[200010];
  scanf("%d%d", &N, &Q);
  for (int i = 0; i < N; i++) {
    scanf("%d", P + i);
    P[i]--;
    P_[P[i]] = i;
  }
  BIT<int> bit(N);
  for (int i = 0; i < Q; i++) {
    scanf("%d%d%d%d", l + i, d + i, r + i, u + i);
    l[i]--;
    d[i]--;
    qs.push_back({d[i], {i, 0}});
    qs.push_back({u[i], {i, 1}});
    qs.push_back({N, {i, 2}});
  }
  sort(qs.begin(), qs.end());
  int t = 0;
  for (int i = 0; i <= N; i++) {
    while (t < Q * 3 && qs[t].first == i) {
      int j = qs[t].second.first;
      int k = qs[t].second.second;
      counter[j][k][0] = bit.query(l[j]);
      counter[j][k][1] = bit.query(r[j]) - counter[j][k][0];
      counter[j][k][2] = i - counter[j][k][0] - counter[j][k][1];
      t++;
    }
    if (i < N) bit.add(P_[i], 1);
  }
  for (int i = 0; i < Q; i++) {
    counter[i][1][0] -= counter[i][0][0];
    counter[i][1][1] -= counter[i][0][1];
    counter[i][1][2] -= counter[i][0][2];
    counter[i][2][0] -= counter[i][0][0] + counter[i][1][0];
    counter[i][2][1] -= counter[i][0][1] + counter[i][1][1];
    counter[i][2][2] -= counter[i][0][2] + counter[i][1][2];
    long long ans = 0;
    for (int a = 0; a < 9; a++) {
      for (int b = a + 1; b < 9; b++) {
        int x1 = a % 3, y1 = a / 3;
        int x2 = b % 3, y2 = b / 3;
        if ((min(x1, x2) <= 1 && 1 <= max(x1, x2)) &&
            (min(y1, y2) <= 1 && 1 <= max(y1, y2))) {
          ans += (long long)counter[i][y1][x1] * counter[i][y2][x2];
        }
      }
    }
    ans += (long long)counter[i][1][1] * (counter[i][1][1] - 1) / 2;
    printf("%lld\n", ans);
  }
  return 0;
}
