分治：归并排序顺手把逆序对数出来

// 逆序对 —— 暴力：每一对都数一遍
//
// 输入：第一行 n，第二行 n 个整数
// 输出：逆序对的个数
//
// 逆序对的定义：一对下标 (i, j)，满足 **i < j 且 a[i] > a[j]**。
// 也就是「排在前面、但数值更大」的那种搭配。
//
// 例：3 1 2 —— 逆序对有 (3,1) 和 (3,2)，一共 2 对。
//
// 它衡量的是「这个序列有多乱」：
//   完全升序 → 0 对（最整齐）
//   完全降序 → n(n-1)/2 对（最乱，任意两个都是逆序）
//
// 暴力就是把每一对都看一遍，O(n²)。n = 5 万时是 12.5 亿次比较。
//
// ⚠ 答案要开 long long！
//   n = 10⁵ 时最多有 n(n-1)/2 ≈ 50 亿对，早就爆 int 了。
//   这是这道题的头号送命点 —— 而且用小数据对拍**根本查不出来**。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) cnt++;

    cout << cnt << "\n";
    return 0;
}

// 逆序对 —— 归并排序顺手数出来
//
// 输入输出和 brute.cpp 完全一样，但是 O(n log n)。
//
// ============ 和第 10 章的归并排序比，只多了一行 ============
//
// 分治的三步（分 → 治 → 合）在这里是：
//     逆序对总数 = 左半边内部的  +  右半边内部的  +  一左一右的
//                  ↑递归解决        ↑递归解决        ↑合并时顺手数
//
// 前两项交给递归（信任它）。关键是第三项：**一个在左半边、一个在右半边**的逆序对。
//
// 合并的时候，两边都已经各自有序了。此刻如果发现 a[i] > a[j]
// （左边当前这个 比 右边当前这个 大，要取右边的），那么：
//
//     **左半边从 i 到 mid 的所有元素都比 a[j] 大**（因为左半边是有序的！）
//     它们都排在 a[j] 前面 —— 于是一口气产生了 (mid - i + 1) 个逆序对。
//
//         左半边: [ 2  5  8 ]        右半边: [ 1  6 ]
//                   ↑i                        ↑j
//                 2 > 1，那么 5、8 也一定 > 1
//                 一次记 3 对，不用一个个数
//
// 这一行 `cnt += mid - i + 1;` 就是这道题的全部。
// **左半边有序**这个条件是它成立的唯一理由 —— 而那正好是递归已经帮我们保证了的。
//
// 这就是分治最漂亮的地方：**排序这件事本身，成了数逆序对的脚手架。**

#include <bits/stdc++.h>
using namespace std;

vector<long long> a, tmp;
long long cnt = 0;

void mergeSort(int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    mergeSort(l, mid);                 // 左半边内部的逆序对（顺便把左半边排好）
    mergeSort(mid + 1, r);             // 右半边内部的逆序对

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];         // 取左边，不构成逆序对
        } else {
            cnt += mid - i + 1;        // ★ 就是这一行：左边剩下的全都比 a[j] 大
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    a.assign(n, 0);
    tmp.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    if (n > 0) mergeSort(0, n - 1);

    cout << cnt << "\n";
    return 0;
}

// 逆序对 —— 把「一口气数一批」的过程打印出来
//
// 输入：n / n 个整数（用小数据，n <= 16）
// 输出：每一次合并时，哪一步一口气数出了多少对逆序对
//
// 跑一遍，重点看带 ★ 的行：
//   每次从右半边取一个元素，就一次性记下「左半边还剩几个」——
//   因为左半边是有序的，剩下的那些一定全都比它大。
//
// 数一数 ★ 出现的次数：它远远少于逆序对的总数。
// **暴力要一对一对地数，分治是一批一批地数** —— 这就是它快的地方。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a, tmp;
long long cnt = 0;
int depth = 0;

void indent() { for (int i = 0; i < depth; i++) cout << "|   "; }

void show(const char* label, int l, int r) {
    cout << label << "[";
    for (int i = l; i <= r; i++) cout << a[i] << (i == r ? "" : " ");
    cout << "]";
}

void mergeSort(int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    depth++;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    depth--;

    indent();
    cout << "合并 [" << l << ", " << r << "]：左 ";
    show("", l, mid);
    cout << "  右 ";
    show("", mid + 1, r);
    cout << "\n";

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            long long add = mid - i + 1;
            indent();
            cout << "   ★ 取右边的 " << a[j] << "：左边还剩 " << add << " 个（";
            for (int p = i; p <= mid; p++) cout << a[p] << (p == mid ? "" : " ");
            cout << "），它们全都比 " << a[j] << " 大 → 一口气记 " << add << " 对\n";
            cnt += add;
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];

    indent();
    cout << "   合并结果 ";
    show("", l, r);
    cout << "　累计逆序对 " << cnt << "\n";
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    if (n <= 0 || n > 16) { cout << "这份是用来看过程的，请用 1 <= n <= 16\n"; return 0; }

    a.assign(n, 0);
    tmp.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << "原数组：";
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n\n";

    mergeSort(0, n - 1);

    cout << "\n逆序对总数 = " << cnt << "\n";
    return 0;
}

// 逆序对 —— 归并排序顺手数出来
//
// 输入输出和 brute.cpp 完全一样，但是 O(n log n)。
//
// ============ 和第 10 章的归并排序比，只多了一行 ============
//
// 分治的三步（分 → 治 → 合）在这里是：
//     逆序对总数 = 左半边内部的  +  右半边内部的  +  一左一右的
//                  ↑递归解决        ↑递归解决        ↑合并时顺手数
//
// 前两项交给递归（信任它）。关键是第三项：**一个在左半边、一个在右半边**的逆序对。
//
// 合并的时候，两边都已经各自有序了。此刻如果发现 a[i] > a[j]
// （左边当前这个 比 右边当前这个 大，要取右边的），那么：
//
//     **左半边从 i 到 mid 的所有元素都比 a[j] 大**（因为左半边是有序的！）
//     它们都排在 a[j] 前面 —— 于是一口气产生了 (mid - i + 1) 个逆序对。
//
//         左半边: [ 2  5  8 ]        右半边: [ 1  6 ]
//                   ↑i                        ↑j
//                 2 > 1，那么 5、8 也一定 > 1
//                 一次记 3 对，不用一个个数
//
// 这一行 `cnt += mid - i + 1;` 就是这道题的全部。
// **左半边有序**这个条件是它成立的唯一理由 —— 而那正好是递归已经帮我们保证了的。
//
// 这就是分治最漂亮的地方：**排序这件事本身，成了数逆序对的脚手架。**

#include <bits/stdc++.h>
using namespace std;

vector<long long> a, tmp;
long long cnt = 0;

void mergeSort(int l, int r) {
    if (l >= r) return;

    int mid = l + (r - l) / 2;
    mergeSort(l, mid);                 // 左半边内部的逆序对（顺便把左半边排好）
    mergeSort(mid + 1, r);             // 右半边内部的逆序对

    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];         // 取左边，不构成逆序对
        } else {
            cnt += mid - i + 1;        // ★ 就是这一行：左边剩下的全都比 a[j] 大
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    a.assign(n, 0);
    tmp.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> a[i];

    if (n > 0) mergeSort(0, n - 1);

    cout << cnt << "\n";
    return 0;
}