#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;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

Ilya is sitting in a waiting area of Metropolis airport and is bored of looking at time table that shows again and again that his plane is delayed. So he took out a sheet of paper and decided to solve some problems.

First Ilya has drawn a grid of size n × n and marked n squares on it, such that no two marked squares share the same row or the same column. He calls a rectangle on a grid with sides parallel to grid sides beautiful if exactly two of its corner squares are marked. There are exactly n·(n - 1) / 2 beautiful rectangles.

Ilya has chosen q query rectangles on a grid with sides parallel to grid sides (not necessarily beautiful ones), and for each of those rectangles he wants to find its beauty degree. Beauty degree of a rectangle is the number of beautiful rectangles that share at least one square with the given one.

Now Ilya thinks that he might not have enough time to solve the problem till the departure of his flight. You are given the description of marked cells and the query rectangles, help Ilya find the beauty degree of each of the query rectangles.

Input

The first line of input contains two integers n and q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the size of the grid and the number of query rectangles.

The second line contains n integers p1, p2, ..., pn, separated by spaces (1 ≤ pi ≤ n, all pi are different), they specify grid squares marked by Ilya: in column i he has marked a square at row pi, rows are numbered from 1 to n, bottom to top, columns are numbered from 1 to n, left to right.

The following q lines describe query rectangles. Each rectangle is described by four integers: l, d, r, u (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ u ≤ n), here l and r are the leftmost and the rightmost columns of the rectangle, d and u the bottommost and the topmost rows of the rectangle.

Output

For each query rectangle output its beauty degree on a separate line.

Examples

Input

2 3
1 2
1 1 1 1
1 1 1 2
1 1 2 2


Output

1
1
1


Input

4 2
1 3 2 4
4 1 4 4
1 1 2 3


Output

3
5

Note

The first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1.

In the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:

<image> <image> <image>

There are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture:

<image> <image> <image> <image> <image>

### Response

```cpp
#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;
}

```