#include <iostream>
#include <vector>
using namespace std;

// Hàm này thực hiện merge hai mảng con đã được sắp xếp là arr[l..m] và arr[m+1..r]
// Đồng thời đếm số nghịch thế trong mảng con arr[l..r]
int countAndMerge(vector<int>& arr, int l, int m, int r) {
    // Số phần tử trong mảng trái và mảng phải
    int n1 = m - l + 1, n2 = r - m;

    // Tạo hai mảng con lưu trữ giá trị từ mảng chính
    vector<int> left(n1), right(n2);
    for (int i = 0; i < n1; i++)
        left[i] = arr[i + l]; // Lấy giá trị từ phần mảng trái
    for (int j = 0; j < n2; j++)
        right[j] = arr[m + 1 + j]; // Lấy giá trị từ phần mảng phải

    // Biến đếm số nghịch thế
    int res = 0;

    // Các chỉ số để duyệt qua mảng trái, mảng phải và mảng chính
    int i = 0, j = 0, k = l;

    // Thực hiện merge hai mảng con
    while (i < n1 && j < n2) {
        // Nếu phần tử bên trái nhỏ hơn hoặc bằng phần tử bên phải
        if (left[i] <= right[j]) {
            arr[k++] = left[i++]; // Gán phần tử bên trái vào mảng chính
        } else {
            // Nếu phần tử bên phải nhỏ hơn
            arr[k++] = right[j++];
            // Tăng số nghịch thế. Vì left[i] > right[j], nên tất cả phần tử từ left[i] đến left[n1-1] 
            // đều tạo thành nghịch thế với right[j].
            res += (n1 - i);
        }
    }

    // Thêm các phần tử còn lại của mảng trái (nếu có)
    while (i < n1)
        arr[k++] = left[i++];

    // Thêm các phần tử còn lại của mảng phải (nếu có)
    while (j < n2)
        arr[k++] = right[j++];

    return res; // Trả về số nghịch thế đã đếm
}

// Hàm đệ quy để đếm số nghịch thế trong mảng
int countInv(vector<int>& arr, int l, int r) {
    int res = 0; // Biến lưu số nghịch thế
    if (l < r) {
        // Tìm vị trí giữa để chia mảng thành hai nửa
        int m = (r + l) / 2;

        // Đệ quy đếm nghịch thế ở nửa bên trái
        res += countInv(arr, l, m);

        // Đệ quy đếm nghịch thế ở nửa bên phải
        res += countInv(arr, m + 1, r);

        // Đếm nghịch thế trong quá trình merge hai nửa
        res += countAndMerge(arr, l, m, r);
    }
    return res; // Trả về tổng số nghịch thế
}

// Hàm tổng quát để đếm nghịch thế trong mảng
int inversionCount(vector<int> &arr) {
    int n = arr.size(); // Kích thước mảng
    return countInv(arr, 0, n - 1); // Gọi hàm đệ quy
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // In ra kết quả là số lượng nghịch thế
    cout << "Number of inversions (O(n log n)): " << inversionCount(arr) << endl;
    return 0;
}