100 1
100 50 99 49 98 48 97 47 96 46 95 45 94 44 93 43 92 42 91 41 90 40 89 39 88 38 87 37 86 36 85 35 84 34 83 33 82 32 81 31 80 30 79 29 78 28 77 27 76 26 75 25 74 24 73 23 72 22 71 21 70 20 69 19 68 18 67 17 66 16 65 15 64 14 63 13 62 12 61 11 60 10 59 9 58 8 57 7 56 6 55 5 54 4 53 3 52 2 51 1
9 8 99 93
 2 9
1 2
1 1 1 1
1 1 1 2
1 2 1 2
1 1 2 1
1 1 2 2
1 2 2 2
2 1 2 1
2 1 2 2
2 2 2 2
 10 10
6 5 7 4 8 3 9 2 10 1
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 10 10
1 10 2 9 3 8 4 7 5 6
4 3 7 10
3 6 8 7
3 2 6 4
1 1 2 8
3 8 10 9
7 3 8 9
4 5 5 9
2 5 6 7
2 5 6 7
1 7 6 10
 10 5
5 10 4 9 3 8 2 7 1 6
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
10 9 8 7 6 5 4 3 2 1
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 7 7
1 2 3 6 7 4 5
3 2 4 6
3 2 5 4
3 6 7 7
1 1 4 4
2 2 7 6
1 2 6 2
1 2 6 7
 10 10
6 1 7 2 8 3 9 4 10 5
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
5 1 6 2 8 3 4 10 9 7
8 1 8 1
1 7 2 7
4 3 8 7
3 7 9 7
7 6 7 7
2 3 10 6
6 4 8 7
1 6 4 7
1 2 5 4
8 5 10 10
 10 10
5 6 4 7 3 8 2 9 1 10
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 10 10
10 5 9 4 8 3 7 2 6 1
8 1 8 1
1 7 2 7
4 3 8 7
3 7 9 7
7 6 7 7
2 3 10 6
6 4 8 7
1 6 4 7
1 2 5 4
8 5 10 10
 10 10
7 5 1 6 10 3 4 8 9 2
4 3 7 10
3 6 8 7
3 2 6 4
1 1 2 8
3 8 10 9
7 3 8 9
4 5 5 9
2 5 6 7
2 5 6 7
1 7 6 10
 10 10
1 2 3 4 5 6 7 8 9 10
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10
 10 10
5 1 6 2 8 3 4 10 9 7
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
9 8 3 4 5 6 7 2 1 10
8 1 8 1
1 7 2 7
4 3 8 7
3 7 9 7
7 6 7 7
2 3 10 6
6 4 8 7
1 6 4 7
1 2 5 4
8 5 10 10
 10 10
10 1 9 2 8 3 7 4 6 5
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
1 1 10 10
 10 10
5 1 6 2 8 3 4 10 9 7
9 5 9 5
4 7 4 7
4 8 5 8
9 1 9 4
4 1 4 6
10 9 10 9
3 5 6 5
3 4 10 4
3 2 5 2
7 8 7 8
 6 10
3 6 1 2 5 4
2 6 2 6
2 3 2 5
6 2 6 2
1 5 1 5
3 5 3 5
2 2 2 4
2 4 5 4
5 4 5 4
1 5 6 5
6 2 6 2
 10 10
1 6 2 7 3 8 4 9 5 10
8 8 8 8
2 1 2 7
8 4 8 4
3 9 3 9
7 7 7 7
2 10 2 10
6 8 9 8
1 4 1 4
1 5 4 5
8 10 8 10

                                                            4886
                                                                1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               1
                                                               11
                                                              17
                                                              15
                                                               6
                                                              16
                                                               2
                                                              19
                                                               4
                                                              20
                                                               8
                                                               39
                                                              30
                                                              26
                                                              16
                                                              23
                                                              29
                                                              27
                                                              30
                                                              30
                                                              27
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                                9
                                                              14
                                                              21
                                                              16
                                                              16
                                                               9
                                                              15
                                                               4
                                                              20
                                                               3
                                                               17
                                                              16
                                                              11
                                                              16
                                                              21
                                                              11
                                                              21
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                                3
                                                               8
                                                              37
                                                              27
                                                              21
                                                              38
                                                              29
                                                              21
                                                              23
                                                              24
                                                               16
                                                              17
                                                              12
                                                               6
                                                              16
                                                               2
                                                              23
                                                               4
                                                              20
                                                               8
                                                                8
                                                              10
                                                              38
                                                              26
                                                              21
                                                              38
                                                              31
                                                              20
                                                              21
                                                              19
                                                               38
                                                              30
                                                              25
                                                              17
                                                              24
                                                              28
                                                              29
                                                              32
                                                              32
                                                              25
                                                               23
                                                              17
                                                              12
                                                               6
                                                              27
                                                               2
                                                              23
                                                               7
                                                              24
                                                               8
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                                8
                                                              14
                                                              38
                                                              27
                                                              19
                                                              38
                                                              29
                                                              20
                                                              23
                                                              19
                                                               45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                              45
                                                               10
                                                              16
                                                              17
                                                               8
                                                              27
                                                               2
                                                              25
                                                              26
                                                              16
                                                              16
                                                                5
                                                               9
                                                               2
                                                               2
                                                               6
                                                               8
                                                              11
                                                               8
                                                               9
                                                               2
                                                               16
                                                              17
                                                              12
                                                               6
                                                              16
                                                               2
                                                              23
                                                               7
                                                              18
                                                               8

#include <bits/stdc++.h>
using namespace std;
template <typename T, class Comparison = std::less<T>>
class cTrackingHeap {
 public:
  cTrackingHeap() : m_c(), m_v() {}
  cTrackingHeap(Comparison c) : m_c(c), m_v() {}
  cTrackingHeap(const cTrackingHeap&) = delete;
  cTrackingHeap& operator=(const cTrackingHeap&) = delete;
  void DecreaseVal(size_t pos, const T& newValue) {
    m_v[pos].first = newValue;
    while (pos > 0) {
      size_t iPar = (pos - 1) / 2;
      if (newValue < m_v[iPar].first) {
        swap(m_v[pos], m_v[iPar]);
        *m_v[pos].second = pos;
        *m_v[iPar].second = iPar;
        pos = iPar;
      } else
        break;
    }
  }
  void Delete(size_t pos) {
    *(m_v[pos].second) = numeric_limits<size_t>::max();
    m_v[pos] = m_v.back();
    m_v.resize(m_v.size() - 1);
    if (pos == m_v.size()) return;
    *(m_v[pos].second) = pos;
    bool makingProgress = true;
    while (makingProgress) {
      makingProgress = false;
      size_t exchangeWith = pos;
      if (2 * pos + 1 < m_v.size() &&
          m_c(m_v[2 * pos + 1].first, m_v[pos].first))
        exchangeWith = 2 * pos + 1;
      if (2 * pos + 2 < m_v.size() &&
          m_c(m_v[2 * pos + 2].first, m_v[exchangeWith].first))
        exchangeWith = 2 * pos + 2;
      if (pos > 0 && m_c(m_v[pos].first, m_v[(pos - 1) / 2].first))
        exchangeWith = (pos - 1) / 2;
      if (exchangeWith != pos) {
        makingProgress = true;
        swap(m_v[pos], m_v[exchangeWith]);
        *m_v[pos].second = pos;
        *m_v[exchangeWith].second = exchangeWith;
        pos = exchangeWith;
      }
    }
  }
  void Insert(const T& value, size_t* posTracker) {
    m_v.push_back(make_pair(value, posTracker));
    *posTracker = m_v.size() - 1;
    size_t pos = m_v.size() - 1;
    bool makingProgress = true;
    while (makingProgress) {
      makingProgress = false;
      if (pos > 0 && m_c(m_v[pos].first, m_v[(pos - 1) / 2].first)) {
        makingProgress = true;
        swap(m_v[pos], m_v[(pos - 1) / 2]);
        *m_v[pos].second = pos;
        *m_v[(pos - 1) / 2].second = (pos - 1) / 2;
        pos = (pos - 1) / 2;
      }
    }
  }
  const T& GetMin() const { return m_v[0].first; }
  const T& Get(size_t i) const { return m_v[i].first; }
  size_t GetSize() const { return m_v.size(); }
  void DropContents() { m_v.clear(); }

 private:
  Comparison m_c;
  vector<pair<T, size_t*>> m_v;
};
int GCD(int a, int b) {
  if (a > b) return GCD(b, a);
  if (a == 0) return b;
  return GCD(a, b % a);
}
void SolveA() {
  int n;
  cin >> n;
  int res = 0;
  for (int i = 0; i < n - i; ++i)
    if (GCD(i, n - i) == 1) res = i;
  cout << res << " " << n - res;
}
void SolveB() {
  int n, k;
  cin >> n >> k;
  cout << ((k == n || k == 0) ? 0 : 1) << " "
       << (2 * k < n - k ? 2 * k : n - k);
}
void SolveC() {
  size_t n, k;
  cin >> n >> k;
  vector<size_t> c(n);
  for (size_t i = 0; i < n; ++i) cin >> c[i];
  vector<size_t> heapPos(n, numeric_limits<size_t>::max());
  cTrackingHeap<pair<size_t, size_t>, greater<pair<size_t, size_t>>> h;
  for (size_t i = 0; i < k; ++i) h.Insert(make_pair(c[i], i), &heapPos[i]);
  vector<size_t> outPos(n);
  unsigned long long ans = 0;
  for (size_t i = 0; i < n; ++i) {
    if (i + k < n) h.Insert(make_pair(c[i + k], i + k), &heapPos[i + k]);
    pair<size_t, size_t> p = h.GetMin();
    size_t cost = p.first;
    size_t j = p.second;
    outPos[j] = i + k + 1;
    ans += static_cast<unsigned long long>(i + k - j) * c[j];
    h.Delete(0);
  }
  cout << ans << "\n";
  for (size_t i = 0; i < n; ++i) cout << outPos[i] << " ";
}
void SolveD() {
  const size_t inf = numeric_limits<size_t>::max();
  size_t n, m, k;
  cin >> n >> m >> k;
  vector<size_t> d(m), f(m), t(m), c(m);
  vector<size_t> iFlight(m), heapPos(m, inf);
  for (size_t i = 0; i < m; ++i) {
    cin >> d[i] >> f[i] >> t[i] >> c[i];
    iFlight[i] = i;
  }
  make_heap(iFlight.begin(), iFlight.end(),
            [&d](size_t i1, size_t i2) -> bool { return d[i1] < d[i2]; });
  sort_heap(iFlight.begin(), iFlight.end(),
            [&d](size_t i1, size_t i2) -> bool { return d[i1] < d[i2]; });
  vector<cTrackingHeap<pair<size_t, size_t>>> inHeaps(n), outHeaps(n);
  for (size_t i = 0; i < m; ++i) {
    if (f[i] == 0)
      outHeaps[f[i] + t[i] - 1].Insert(make_pair(c[i], i), &heapPos[i]);
  }
  size_t nArrived = 0;
  size_t i1 = 0, i2 = 0;
  unsigned long long curInCost = 0;
  unsigned long long ans = numeric_limits<unsigned long long>::max();
  unsigned long long curOutCost = 0;
  bool canFlyOut = true;
  for (size_t i = 0; i < n; ++i)
    if (outHeaps[i].GetSize() == 0)
      canFlyOut = false;
    else
      curOutCost += outHeaps[i].GetMin().first;
  while (i1 < m) {
    size_t j = i1;
    while (j + 1 < m && d[iFlight[i1]] == d[iFlight[j + 1]]) ++j;
    size_t inCount = 0;
    for (size_t k = i1; k <= j; ++k) {
      size_t nf = iFlight[k];
      if (f[nf] == 0) continue;
      ++inCount;
      size_t iPerson = f[nf] + t[nf] - 1;
      if (inHeaps[iPerson].GetSize() == 0)
        ++nArrived;
      else
        curInCost -= inHeaps[iPerson].GetMin().first;
      inHeaps[iPerson].Insert(make_pair(c[nf], nf), &heapPos[nf]);
      curInCost += inHeaps[iPerson].GetMin().first;
    }
    while (i2 < m && d[iFlight[i2]] - d[iFlight[i1]] <= k) {
      size_t nf = iFlight[i2];
      if (f[nf] == 0) {
        size_t iPerson = t[nf] - 1;
        curOutCost -= outHeaps[iPerson].GetMin().first;
        outHeaps[iPerson].Delete(heapPos[nf]);
        if (outHeaps[iPerson].GetSize() == 0)
          canFlyOut = false;
        else
          curOutCost += outHeaps[iPerson].GetMin().first;
      }
      ++i2;
    }
    if (!canFlyOut) break;
    if (nArrived == n) ans = min(ans, curInCost + curOutCost);
    i1 = j + 1;
  }
  if (ans == numeric_limits<unsigned long long>::max())
    cout << -1;
  else
    cout << ans;
}
struct sPersistentTreeNode {
  sPersistentTreeNode() {
    val = r = l = iLeft = iRight = std::numeric_limits<unsigned>::max();
  }
  sPersistentTreeNode(unsigned val_, unsigned l_, unsigned r_, unsigned iLeft_,
                      unsigned iRight_)
      : val(val_), r(r_), l(l_), iLeft(iLeft_), iRight(iRight_) {}
  unsigned val, r, l, iLeft, iRight;
};
size_t CreateSubtree(vector<sPersistentTreeNode>& t, size_t l, size_t r) {
  if (l == r) {
    t.push_back(sPersistentTreeNode(0, l, l, -1, -1));
  } else {
    size_t m = (l + r) / 2;
    size_t iLeft = CreateSubtree(t, l, m);
    size_t iRight = CreateSubtree(t, m + 1, r);
    t.push_back(sPersistentTreeNode(0, l, r, iLeft, iRight));
  }
  return t.size() - 1;
}
size_t Increment(vector<sPersistentTreeNode>& t, size_t iNode, size_t pos,
                 size_t inc) {
  sPersistentTreeNode n = t[iNode];
  n.val += inc;
  if (n.l != n.r) {
    unsigned m = (n.l + n.r) / 2;
    if (pos <= m)
      n.iLeft = Increment(t, n.iLeft, pos, inc);
    else
      n.iRight = Increment(t, n.iRight, pos, inc);
  }
  t.push_back(n);
  return t.size() - 1;
}
size_t GetSum(const vector<sPersistentTreeNode>& t, size_t iNode, size_t l,
              size_t r) {
  const sPersistentTreeNode& n = t[iNode];
  if (n.l >= l && n.r <= r)
    return n.val;
  else if (n.l > r || n.r < l)
    return 0;
  else
    return GetSum(t, n.iLeft, l, r) + GetSum(t, n.iRight, l, r);
}
void SolveE() {
  int n, q;
  scanf("%d%d", &n, &q);
  vector<sPersistentTreeNode> t;
  t.reserve(2 * n * 20);
  vector<size_t> roots(n + 1);
  roots[0] = CreateSubtree(t, 1, n);
  for (size_t i = 0; i < n; ++i) {
    int row;
    scanf("%d", &row);
    roots[i + 1] = Increment(t, roots[i], row, 1);
  }
  for (size_t i = 0; i < q; ++i) {
    int l, d, r, u;
    scanf("%d%d%d%d", &l, &d, &r, &u);
    size_t cnt[3][3] = {0};
    if (l > 1) {
      if (d > 1) cnt[0][0] = GetSum(t, roots[l - 1], 1, d - 1);
      cnt[0][1] = GetSum(t, roots[l - 1], d, u);
      cnt[0][2] = l - 1 - cnt[0][1] - cnt[0][0];
    }
    if (d > 1) cnt[1][0] = GetSum(t, roots[r], 1, d - 1);
    cnt[1][1] = GetSum(t, roots[r], d, u);
    cnt[1][2] = r - cnt[1][1] - cnt[1][0];
    if (r < n) {
      if (d > 1) cnt[2][0] = GetSum(t, roots[n], 1, d - 1);
      cnt[2][1] = GetSum(t, roots[n], d, u);
      cnt[2][2] = n - cnt[2][1] - cnt[2][0];
    } else
      for (size_t i = 0; i < 3; ++i) cnt[2][i] = cnt[1][i];
    for (size_t i = 2; i > 0; --i)
      for (size_t j = 0; j < 3; ++j) cnt[i][j] -= cnt[i - 1][j];
    long long res = (static_cast<long long>(cnt[1][1]) * (cnt[1][1] - 1)) / 2;
    res += static_cast<long long>(cnt[0][2]) *
           (cnt[1][0] + cnt[1][1] + cnt[2][0] + cnt[2][1]);
    res +=
        static_cast<long long>(cnt[0][1]) *
        (cnt[1][2] + cnt[1][1] + cnt[1][0] + cnt[2][2] + cnt[2][1] + cnt[2][0]);
    res += static_cast<long long>(cnt[0][0]) *
           (cnt[1][2] + cnt[1][1] + cnt[2][2] + cnt[2][1]);
    res += static_cast<long long>(cnt[1][2]) *
           (cnt[1][1] + cnt[1][0] + cnt[2][1] + cnt[2][0]);
    res += static_cast<long long>(cnt[1][1]) *
           (cnt[1][0] + cnt[2][2] + cnt[2][1] + cnt[2][0]);
    res += static_cast<long long>(cnt[1][0]) * (cnt[2][2] + cnt[2][1]);
    printf("%I64d\n", res);
  }
}
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  SolveE();
  return 0;
}
