#include <bits/stdc++.h>
using namespace std;
int p[200200], pr[200200];
int ql[200200], qr[200200], qt[200200], qb[200200];
unordered_map<int, unordered_map<int, int>> isord;
unordered_map<int, unordered_map<int, int>> sol;
vector<pair<int, int>> ord;
const int mx = (1 << 18);
int tree[2 * mx];
void update(int i) {
  while (i >>= 1) {
    tree[i] = tree[i << 1] + tree[i << 1 | 1];
  }
}
int query(int i, int u, int v, int l, int r) {
  if (l <= u && v <= r) {
    return tree[i];
  }
  int mid = (u + v) / 2, ans = 0;
  if (l < mid) ans += query(i << 1, u, mid, l, r);
  if (mid < r) ans += query(i << 1 | 1, mid, v, l, r);
  return ans;
}
void put(int r, int c) {
  if (r > 0 && c > 0 && !isord[r][c]) {
    isord[r][c] = 1;
    ord.push_back(make_pair(r, c));
  }
}
int main() {
  int n, q;
  scanf("%d%d", &(n), &(q));
  for (int i = 1; i <= n; i++) {
    scanf("%d", &(p[i]));
    pr[p[i]] = i;
  }
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &(ql[i]), &(qt[i]));
    scanf("%d%d", &(qr[i]), &(qb[i]));
    put(qb[i], ql[i] - 1);
    put(qt[i] - 1, qr[i]);
    put(qb[i], qr[i]);
    put(qt[i] - 1, ql[i] - 1);
  }
  sort(ord.begin(), ord.end());
  int j = 0;
  for (int ro = 1; ro <= n; ro++) {
    tree[mx + pr[ro]] = 1;
    update(mx + pr[ro]);
    while (j < ord.size() && ord[j].first < ro) j++;
    while (ord[j].first == ro) {
      int qans = query(1, mx, mx << 1, mx + 1, mx + ord[j].second + 1);
      sol[ord[j].first][ord[j].second] = qans;
      j++;
    }
  }
  for (int i = 1; i <= q; i++) {
    int r = qr[i], l = ql[i], t = qt[i], b = qb[i];
    long long ins =
        sol[b][r] - sol[b][l - 1] - sol[t - 1][r] + sol[t - 1][l - 1];
    long long ans = ins * (n - ins) + ins * (ins - 1) / 2;
    vector<int> x;
    x.push_back(sol[t - 1][l - 1]);
    x.push_back(sol[t - 1][r] - sol[t - 1][l - 1]);
    x.push_back(t - 1 - sol[t - 1][r]);
    x.push_back(sol[b][l - 1] - sol[t - 1][l - 1]);
    x.push_back(b - sol[b][r] - (t - 1) + sol[t - 1][r]);
    x.push_back(l - 1 - sol[b][l - 1]);
    x.push_back(r - (l - 1) - sol[b][r] + sol[b][l - 1]);
    x.push_back(n - r - b + sol[b][r]);
    long long ans2 = 0;
    ans2 += 1LL * x[0] * (x[4] + x[6] + x[7]);
    ans2 += 1LL * x[1] * (n - (t - 1) - ins);
    ans2 += 1LL * x[2] * (x[3] + x[5] + x[6]);
    ans2 += 1LL * x[3] * (n - (l - 1) - ins);
    ans2 += 1LL * x[4] * (r - ins);
    ans2 += 1LL * x[5] * (x[1] + x[2] + x[4]);
    ans2 += 1LL * x[6] * (b - ins);
    ans2 += 1LL * x[7] * (x[0] + x[1] + x[3]);
    ans += ans2 / 2;
    printf(
        "%lld"
        "\n",
        ans);
  }
  return 0;
}
