#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; // The Fenwick Tree (BIT) Structure struct FenwickTree { int n; vector<int> tree; FenwickTree(int n) : n(n), tree(n + 1, 0) {} // Adds 1 to the frequency of a certain height void update(int i, int delta) { for (; i <= n; i += i & -i) { tree[i] += delta; } } // Queries how many mountains have been seen up to height i int query(int i) { int sum = 0; for (; i > 0; i -= i & -i) { sum += tree[i]; } return sum; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; if (!(cin >> n)) return 0; vector<int> a(n); vector<int> coords; for (int i = 0; i < n; i++) { cin >> a[i]; coords.push_back(a[i]); } // --- Coordinate Compression --- // This turns heights like [100, 999, 50] into [2, 3, 1] sort(coords.begin(), coords.end()); coords.erase(unique(coords.begin(), coords.end()), coords.end()); for (int i = 0; i < n; i++) { a[i] = lower_bound(coords.begin(), coords.end(), a[i]) - coords.begin() + 1; } int maxHeight = coords.size(); vector<int> left_count(n), right_count(n); // --- Step 1: Count smaller elements to the left --- FenwickTree ft_left(maxHeight); for (int i = 0; i < n; i++) { left_count[i] = ft_left.query(a[i] - 1); ft_left.update(a[i], 1); } // --- Step 2: Count smaller elements to the right --- FenwickTree ft_right(maxHeight); for (int i = n - 1; i >= 0; i--) { right_count[i] = ft_right.query(a[i] - 1); ft_right.update(a[i], 1); } // --- Step 3: Calculate total combinations --- ll total = 0; for (int i = 0; i < n; i++) { total += (ll)left_count[i] * right_count[i]; } cout << total << endl; return 0; }