#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int arr = 2e5 + 10;
const int ar = 2e3 + 10;
const long double pi = acos(-1);
const long double eps = 1e-10;
const long long md = 1e9 + 7;
int f[arr];
void upd(int pos, int val) {
  for (int i = pos; i < arr; i |= i + 1) {
    f[i] += val;
  }
}
int get(int pos) {
  int res = 0;
  for (int i = pos; i >= 0; i &= (i + 1), i--) {
    res += f[i];
  }
  return res;
}
int get(int l, int r) { return get(r) - get(l - 1); }
vector<pair<pair<int, int>, int>> in[arr];
vector<pair<pair<int, int>, int>> out[arr];
void add(int x1, int y1, int x2, int y2, int num) {
  in[x1].push_back(make_pair(make_pair(y1, y2), num));
  out[x2].push_back(make_pair(make_pair(y1, y2), num));
}
int ans1[20 * arr];
int kek[arr];
int n, q;
void big_do() {
  for (int i = 0; i <= n + 1; i++) {
    for (auto j : in[i]) {
      ans1[j.second] -= get(j.first.first, j.first.second);
    }
    if (1 <= i && i <= n) {
      upd(kek[i], +1);
    }
    for (auto j : out[i]) {
      ans1[j.second] += get(j.first.first, j.first.second);
    }
  }
}
vector<int> ans[arr];
int main() {
  "" != "" ? freopen(
                 ""
                 ".in",
                 "r", stdin),
      freopen(
          ""
          ".out",
          "w", stdout)
           : 0;
  "" != "" ? freopen(
                 ""
                 ".dat",
                 "r", stdin),
      freopen(
          ""
          ".sol",
          "w", stdout)
           : 0;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &kek[i]);
  }
  int last = 0;
  for (int i = 1; i <= q; i++) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    add(1, 1, x1 - 1, y1 - 1, last);
    ans[i].push_back(last);
    last++;
    add(x1, y1, n, n, last);
    ans[i].push_back(last);
    last++;
    add(1, y1, x1 - 1, y2, last);
    ans[i].push_back(last);
    last++;
    add(x1, 1, n, n, last);
    ans[i].push_back(last);
    last++;
    add(1, y2 + 1, x1 - 1, n, last);
    ans[i].push_back(last);
    last++;
    add(x1, 1, n, y2, last);
    ans[i].push_back(last);
    last++;
    add(x1, y2 + 1, x2, n, last);
    ans[i].push_back(last);
    last++;
    add(1, 1, n, y2, last);
    ans[i].push_back(last);
    last++;
    add(x2 + 1, y2 + 1, n, n, last);
    ans[i].push_back(last);
    last++;
    add(1, 1, x2, y2, last);
    ans[i].push_back(last);
    last++;
    add(x2 + 1, y1, n, y2, last);
    ans[i].push_back(last);
    last++;
    add(1, 1, x2, n, last);
    ans[i].push_back(last);
    last++;
    add(x2 + 1, 1, n, y1 - 1, last);
    ans[i].push_back(last);
    last++;
    add(1, y1, x2, n, last);
    ans[i].push_back(last);
    last++;
    add(x1, 1, x2, y1 - 1, last);
    ans[i].push_back(last);
    last++;
    add(1, y1, n, n, last);
    ans[i].push_back(last);
    last++;
    add(x1, y1, x2, y2, last);
    ans[i].push_back(last);
    last++;
  }
  big_do();
  for (int i = 1; i <= q; i++) {
    long long res = 0;
    for (int j = 0; j < 16; j += 2) {
      res += 1ll * ans1[ans[i][j]] * ans1[ans[i][j + 1]];
    }
    long long lol = ans1[ans[i][16]];
    res += lol * (lol - 1);
    res += lol * (n - lol);
    res /= 2;
    cout << res << "\n";
  }
}
