#include <bits/stdc++.h>
using namespace std;
int n, q;
int bit[200005];
vector<pair<int, pair<pair<int, int>, pair<int, int> > > > type[4];
long long res[200005];
pair<int, int> a[200005], b[200005];
bool check(int x1, int y1, int x2, int y2) {
  if (x1 <= 0 || x1 > n) return false;
  if (y1 <= 0 || y1 > n) return false;
  if (x2 <= 0 || x2 > n) return false;
  if (y2 <= 0 || y2 > n) return false;
  return true;
}
void update(int x) {
  while (x <= n) {
    bit[x]++;
    x += (x & (-x));
  }
}
int get(int x, int y) {
  int sum = 0;
  while (y != 0) {
    sum += bit[y];
    y = y & (y - 1);
  }
  x--;
  while (x != 0) {
    sum -= bit[x];
    x = x & (x - 1);
  }
  return sum;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    int y;
    cin >> y;
    a[i] = pair<int, int>(i, y);
    b[i] = pair<int, int>(y, i);
  }
  sort(b + 1, b + 1 + n);
  for (int i = 1; i <= q; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    long long res = 0LL, z;
    if (check(1, 1, x1 - 1, n))
      type[0].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          x1 - 1, pair<pair<int, int>, pair<int, int> >(pair<int, int>(1, n),
                                                        pair<int, int>(1, i))));
    if (check(x2 + 1, 1, n, n))
      type[1].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          x2 + 1, pair<pair<int, int>, pair<int, int> >(pair<int, int>(1, n),
                                                        pair<int, int>(1, i))));
    if (check(1, 1, n, y1 - 1))
      type[2].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          y1 - 1, pair<pair<int, int>, pair<int, int> >(pair<int, int>(1, n),
                                                        pair<int, int>(1, i))));
    if (check(1, y2 + 1, n, n))
      type[3].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          y2 + 1, pair<pair<int, int>, pair<int, int> >(pair<int, int>(1, n),
                                                        pair<int, int>(1, i))));
    if (check(1, 1, x1 - 1, y1 - 1))
      type[0].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          x1 - 1, pair<pair<int, int>, pair<int, int> >(
                      pair<int, int>(1, y1 - 1), pair<int, int>(-1, i))));
    if (check(x2 + 1, 1, n, y1 - 1))
      type[1].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          x2 + 1, pair<pair<int, int>, pair<int, int> >(
                      pair<int, int>(1, y1 - 1), pair<int, int>(-1, i))));
    if (check(1, y2 + 1, x1 - 1, n))
      type[0].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          x1 - 1, pair<pair<int, int>, pair<int, int> >(
                      pair<int, int>(y2 + 1, n), pair<int, int>(-1, i))));
    if (check(x2 + 1, y2 + 1, n, n))
      type[1].push_back(pair<int, pair<pair<int, int>, pair<int, int> > >(
          x2 + 1, pair<pair<int, int>, pair<int, int> >(
                      pair<int, int>(y2 + 1, n), pair<int, int>(-1, i))));
  }
  for (int i = 0; i < (int)type[1].size(); i++) type[1][i].first *= -1;
  for (int i = 0; i < (int)type[3].size(); i++) type[3][i].first *= -1;
  for (int i = 0; i <= 3; i++) sort(type[i].begin(), type[i].end());
  int last;
  memset(bit, 0, sizeof bit);
  last = 0;
  for (int x = 1; x <= n; x++) {
    update(a[x].second);
    while (last < (int)type[0].size() && type[0][last].first == x) {
      long long val = (long long)get(type[0][last].second.first.first,
                                     type[0][last].second.first.second);
      res[type[0][last].second.second.second] +=
          (long long)type[0][last].second.second.first * val * (val - 1) / 2LL;
      last++;
    }
  }
  memset(bit, 0, sizeof bit);
  last = 0;
  for (int x = n; x >= 1; x--) {
    update(a[x].second);
    while (last < (int)type[1].size() && type[1][last].first == -x) {
      long long val = (long long)get(type[1][last].second.first.first,
                                     type[1][last].second.first.second);
      res[type[1][last].second.second.second] +=
          (long long)type[1][last].second.second.first * val * (val - 1) / 2LL;
      last++;
    }
  }
  memset(bit, 0, sizeof bit);
  last = 0;
  for (int x = 1; x <= n; x++) {
    update(b[x].second);
    while (last < (int)type[2].size() && type[2][last].first == x) {
      long long val = (long long)get(type[2][last].second.first.first,
                                     type[2][last].second.first.second);
      res[type[2][last].second.second.second] +=
          (long long)type[2][last].second.second.first * val * (val - 1) / 2LL;
      last++;
    }
  }
  memset(bit, 0, sizeof bit);
  last = 0;
  for (int x = n; x >= 1; x--) {
    update(b[x].second);
    while (last < (int)type[3].size() && type[3][last].first == -x) {
      long long val = (long long)get(type[3][last].second.first.first,
                                     type[3][last].second.first.second);
      res[type[3][last].second.second.second] +=
          (long long)type[3][last].second.second.first * val * (val - 1) / 2LL;
      last++;
    }
  }
  for (int i = 1; i <= q; i++)
    cout << (long long)n * (long long)(n - 1) / 2 - res[i] << "\n";
  return 0;
}
