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

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gSMOgbSBuw6B5IHRo4buxYyBoaeG7h24gbWVyZ2UgaGFpIG3huqNuZyBjb24gxJHDoyDEkcaw4bujYyBz4bqvcCB44bq/cCBsw6AgYXJyW2wuLm1dIHbDoCBhcnJbbSsxLi5yXQovLyDEkOG7k25nIHRo4budaSDEkeG6v20gc+G7kSBuZ2jhu4tjaCB0aOG6vyB0cm9uZyBt4bqjbmcgY29uIGFycltsLi5yXQppbnQgY291bnRBbmRNZXJnZSh2ZWN0b3I8aW50PiYgYXJyLCBpbnQgbCwgaW50IG0sIGludCByKSB7CiAgICAvLyBT4buRIHBo4bqnbiB04butIHRyb25nIG3huqNuZyB0csOhaSB2w6AgbeG6o25nIHBo4bqjaQogICAgaW50IG4xID0gbSAtIGwgKyAxLCBuMiA9IHIgLSBtOwoKICAgIC8vIFThuqFvIGhhaSBt4bqjbmcgY29uIGzGsHUgdHLhu68gZ2nDoSB0cuG7iyB04burIG3huqNuZyBjaMOtbmgKICAgIHZlY3RvcjxpbnQ+IGxlZnQobjEpLCByaWdodChuMik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG4xOyBpKyspCiAgICAgICAgbGVmdFtpXSA9IGFycltpICsgbF07IC8vIEzhuqV5IGdpw6EgdHLhu4sgdOG7qyBwaOG6p24gbeG6o25nIHRyw6FpCiAgICBmb3IgKGludCBqID0gMDsgaiA8IG4yOyBqKyspCiAgICAgICAgcmlnaHRbal0gPSBhcnJbbSArIDEgKyBqXTsgLy8gTOG6pXkgZ2nDoSB0cuG7iyB04burIHBo4bqnbiBt4bqjbmcgcGjhuqNpCgogICAgLy8gQmnhur9uIMSR4bq/bSBz4buRIG5naOG7i2NoIHRo4bq/CiAgICBpbnQgcmVzID0gMDsKCiAgICAvLyBDw6FjIGNo4buJIHPhu5EgxJHhu4MgZHV54buHdCBxdWEgbeG6o25nIHRyw6FpLCBt4bqjbmcgcGjhuqNpIHbDoCBt4bqjbmcgY2jDrW5oCiAgICBpbnQgaSA9IDAsIGogPSAwLCBrID0gbDsKCiAgICAvLyBUaOG7sWMgaGnhu4duIG1lcmdlIGhhaSBt4bqjbmcgY29uCiAgICB3aGlsZSAoaSA8IG4xICYmIGogPCBuMikgewogICAgICAgIC8vIE7hur91IHBo4bqnbiB04butIGLDqm4gdHLDoWkgbmjhu48gaMahbiBob+G6t2MgYuG6sW5nIHBo4bqnbiB04butIGLDqm4gcGjhuqNpCiAgICAgICAgaWYgKGxlZnRbaV0gPD0gcmlnaHRbal0pIHsKICAgICAgICAgICAgYXJyW2srK10gPSBsZWZ0W2krK107IC8vIEfDoW4gcGjhuqduIHThu60gYsOqbiB0csOhaSB2w6BvIG3huqNuZyBjaMOtbmgKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAvLyBO4bq/dSBwaOG6p24gdOG7rSBiw6puIHBo4bqjaSBuaOG7jyBoxqFuCiAgICAgICAgICAgIGFycltrKytdID0gcmlnaHRbaisrXTsKICAgICAgICAgICAgLy8gVMSDbmcgc+G7kSBuZ2jhu4tjaCB0aOG6vy4gVsOsIGxlZnRbaV0gPiByaWdodFtqXSwgbsOqbiB04bqldCBj4bqjIHBo4bqnbiB04butIHThu6sgbGVmdFtpXSDEkeG6v24gbGVmdFtuMS0xXSAKICAgICAgICAgICAgLy8gxJHhu4F1IHThuqFvIHRow6BuaCBuZ2jhu4tjaCB0aOG6vyB24bubaSByaWdodFtqXS4KICAgICAgICAgICAgcmVzICs9IChuMSAtIGkpOwogICAgICAgIH0KICAgIH0KCiAgICAvLyBUaMOqbSBjw6FjIHBo4bqnbiB04butIGPDsm4gbOG6oWkgY+G7p2EgbeG6o25nIHRyw6FpIChu4bq/dSBjw7MpCiAgICB3aGlsZSAoaSA8IG4xKQogICAgICAgIGFycltrKytdID0gbGVmdFtpKytdOwoKICAgIC8vIFRow6ptIGPDoWMgcGjhuqduIHThu60gY8OybiBs4bqhaSBj4bunYSBt4bqjbmcgcGjhuqNpIChu4bq/dSBjw7MpCiAgICB3aGlsZSAoaiA8IG4yKQogICAgICAgIGFycltrKytdID0gcmlnaHRbaisrXTsKCiAgICByZXR1cm4gcmVzOyAvLyBUcuG6oyB24buBIHPhu5Egbmdo4buLY2ggdGjhur8gxJHDoyDEkeG6v20KfQoKLy8gSMOgbSDEkeG7hyBxdXkgxJHhu4MgxJHhur9tIHPhu5Egbmdo4buLY2ggdGjhur8gdHJvbmcgbeG6o25nCmludCBjb3VudEludih2ZWN0b3I8aW50PiYgYXJyLCBpbnQgbCwgaW50IHIpIHsKICAgIGludCByZXMgPSAwOyAvLyBCaeG6v24gbMawdSBz4buRIG5naOG7i2NoIHRo4bq/CiAgICBpZiAobCA8IHIpIHsKICAgICAgICAvLyBUw6xtIHbhu4sgdHLDrSBnaeG7r2EgxJHhu4MgY2hpYSBt4bqjbmcgdGjDoG5oIGhhaSBu4butYQogICAgICAgIGludCBtID0gKHIgKyBsKSAvIDI7CgogICAgICAgIC8vIMSQ4buHIHF1eSDEkeG6v20gbmdo4buLY2ggdGjhur8g4bufIG7hu61hIGLDqm4gdHLDoWkKICAgICAgICByZXMgKz0gY291bnRJbnYoYXJyLCBsLCBtKTsKCiAgICAgICAgLy8gxJDhu4cgcXV5IMSR4bq/bSBuZ2jhu4tjaCB0aOG6vyDhu58gbuG7rWEgYsOqbiBwaOG6o2kKICAgICAgICByZXMgKz0gY291bnRJbnYoYXJyLCBtICsgMSwgcik7CgogICAgICAgIC8vIMSQ4bq/bSBuZ2jhu4tjaCB0aOG6vyB0cm9uZyBxdcOhIHRyw6xuaCBtZXJnZSBoYWkgbuG7rWEKICAgICAgICByZXMgKz0gY291bnRBbmRNZXJnZShhcnIsIGwsIG0sIHIpOwogICAgfQogICAgcmV0dXJuIHJlczsgLy8gVHLhuqMgduG7gSB04buVbmcgc+G7kSBuZ2jhu4tjaCB0aOG6vwp9CgovLyBIw6BtIHThu5VuZyBxdcOhdCDEkeG7gyDEkeG6v20gbmdo4buLY2ggdGjhur8gdHJvbmcgbeG6o25nCmludCBpbnZlcnNpb25Db3VudCh2ZWN0b3I8aW50PiAmYXJyKSB7CiAgICBpbnQgbiA9IGFyci5zaXplKCk7IC8vIEvDrWNoIHRoxrDhu5tjIG3huqNuZwogICAgcmV0dXJuIGNvdW50SW52KGFyciwgMCwgbiAtIDEpOyAvLyBH4buNaSBow6BtIMSR4buHIHF1eQp9CgppbnQgbWFpbigpIHsKICAgIGludCBuOwogICAgY2luID4+IG47CiAgICB2ZWN0b3I8aW50PiBhcnIobik7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIGNpbiA+PiBhcnJbaV07CiAgICB9CiAgICAvLyBJbiByYSBr4bq/dCBxdeG6oyBsw6Agc+G7kSBsxrDhu6NuZyBuZ2jhu4tjaCB0aOG6vwogICAgY291dCA8PCAiTnVtYmVyIG9mIGludmVyc2lvbnMgKE8obiBsb2cgbikpOiAiIDw8IGludmVyc2lvbkNvdW50KGFycikgPDwgZW5kbDsKICAgIHJldHVybiAwOwp9

NgoxIDIgNCAzIDUgMQo=

6
1 2 4 3 5 1