// Ordenamientos que solo miran los datos a través de una comparación, y un comparador
// que cuenta. Así se puede medir exactamente lo que habla la cota inferior.
#pragma once

#include <cstddef>
#include <string>
#include <utility>
#include <vector>

// Compara y anota: cuántas comparaciones van y qué respondió cada una.
// La cadena de respuestas identifica la hoja del árbol de decisiones a la que se llega.
class CountingLess {
public:
    bool operator()(int a, int b) {
        count_++;
        const bool answer = a < b;
        path_ += answer ? 'S' : 'N';
        return answer;
    }

    long long count() const { return count_; }
    const std::string& path() const { return path_; }

private:
    long long count_ = 0;
    std::string path_;
};

// Ordena tres valores con a lo sumo 3 comparaciones.
inline void sort_three(std::vector<int>& a, CountingLess& less) {
    if (less(a[1], a[0])) std::swap(a[0], a[1]);
    // Ahora a[0] < a[1]. Falta ubicar a[2].
    if (less(a[2], a[1])) {
        std::swap(a[1], a[2]);
        if (less(a[1], a[0])) std::swap(a[0], a[1]);
    }
}

inline void insertion_sort(std::vector<int>& a, CountingLess& less) {
    for (std::size_t i = 1; i < a.size(); i++) {
        const int value = a[i];
        std::size_t j = i;
        while (j > 0 && less(value, a[j - 1])) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = value;
    }
}

// Mergesort sobre el rango semiabierto [lo, hi).
inline void merge_sort_range(std::vector<int>& a, std::size_t lo, std::size_t hi, CountingLess& less) {
    if (hi - lo < 2) return;
    const std::size_t mid = lo + (hi - lo) / 2;
    merge_sort_range(a, lo, mid, less);
    merge_sort_range(a, mid, hi, less);
    std::vector<int> merged;
    merged.reserve(hi - lo);
    std::size_t i = lo;
    std::size_t j = mid;
    while (i < mid && j < hi) {
        if (less(a[j], a[i])) {
            merged.push_back(a[j++]);
        } else {
            merged.push_back(a[i++]);
        }
    }
    while (i < mid) merged.push_back(a[i++]);
    while (j < hi) merged.push_back(a[j++]);
    for (std::size_t k = 0; k < merged.size(); k++) a[lo + k] = merged[k];
}

inline void merge_sort(std::vector<int>& a, CountingLess& less) {
    merge_sort_range(a, 0, a.size(), less);
}

// El menor h con 2^h ≥ n!, con enteros. Sirve hasta n = 20, porque 20! cabe en 64 bits.
inline int ceil_log2_factorial(int n) {
    unsigned long long factorial = 1;
    for (int i = 2; i <= n; i++) factorial *= static_cast<unsigned long long>(i);
    int h = 0;
    unsigned long long power = 1;
    while (power < factorial) {
        power *= 2;
        h++;
    }
    return h;
}