// Inversiones por fuerza bruta: se revisan todos los pares. Cuesta Θ(n²).
#pragma once

#include <cstddef>
#include <vector>

inline long long count_inversions_brute(const std::vector<int>& a, std::size_t lo, std::size_t hi) {
    long long count = 0;
    for (std::size_t i = lo; i < hi; i++) {
        for (std::size_t j = i + 1; j < hi; j++) {
            if (a[i] > a[j]) {
                count++;
            }
        }
    }
    return count;
}

inline long long count_inversions_brute(const std::vector<int>& a) {
    return count_inversions_brute(a, 0, a.size());
}

// Pares (x, y) con x en a[lo, mid), y en a[mid, hi) y x > y.
inline long long count_cross_brute(const std::vector<int>& a, std::size_t lo, std::size_t mid, std::size_t hi) {
    long long count = 0;
    for (std::size_t i = lo; i < mid; i++) {
        for (std::size_t j = mid; j < hi; j++) {
            if (a[i] > a[j]) {
                count++;
            }
        }
    }
    return count;
}