// Un adversario para ordenamientos por comparaciones. No fija la entrada de antemano: guarda todas
// las permutaciones que siguen siendo posibles, y a cada pregunta responde lo que deja más.
#pragma once

#include <algorithm>
#include <cstddef>
#include <numeric>
#include <vector>

class Adversary {
public:
    explicit Adversary(int n) {
        std::vector<int> p(static_cast<std::size_t>(n));
        std::iota(p.begin(), p.end(), 0);
        do {
            alive_.push_back(p);
        } while (std::next_permutation(p.begin(), p.end()));
    }

    // ¿El elemento i es menor que el j? i y j son posiciones de la entrada.
    bool less(int i, int j) {
        count_++;
        std::vector<std::vector<int>> yes;
        std::vector<std::vector<int>> no;
        for (const std::vector<int>& p : alive_) {
            if (p[static_cast<std::size_t>(i)] < p[static_cast<std::size_t>(j)]) {
                yes.push_back(p);
            } else {
                no.push_back(p);
            }
        }
        const bool answer = yes.size() >= no.size();
        alive_ = answer ? std::move(yes) : std::move(no);
        return answer;
    }

    long long count() const { return count_; }
    std::size_t alive() const { return alive_.size(); }
    // Una entrada que es coherente con todas las respuestas dadas hasta ahora.
    const std::vector<int>& witness() const { return alive_.front(); }

private:
    std::vector<std::vector<int>> alive_;
    long long count_ = 0;
};

// Ordena las posiciones 0..n-1 preguntando a Compare, con inserción.
template <typename Compare>
std::vector<int> insertion_order(int n, Compare is_less) {
    std::vector<int> order(static_cast<std::size_t>(n));
    std::iota(order.begin(), order.end(), 0);
    for (std::size_t i = 1; i < order.size(); i++) {
        const int value = order[i];
        std::size_t j = i;
        while (j > 0 && is_less(value, order[j - 1])) {
            order[j] = order[j - 1];
            j--;
        }
        order[j] = value;
    }
    return order;
}

template <typename Compare>
void merge_range(std::vector<int>& order, std::size_t lo, std::size_t hi, Compare& is_less) {
    if (hi - lo < 2) return;
    const std::size_t mid = lo + (hi - lo) / 2;
    merge_range(order, lo, mid, is_less);
    merge_range(order, mid, hi, is_less);
    std::vector<int> merged;
    std::size_t i = lo;
    std::size_t j = mid;
    while (i < mid && j < hi) {
        if (is_less(order[j], order[i])) {
            merged.push_back(order[j++]);
        } else {
            merged.push_back(order[i++]);
        }
    }
    while (i < mid) merged.push_back(order[i++]);
    while (j < hi) merged.push_back(order[j++]);
    std::copy(merged.begin(), merged.end(), order.begin() + static_cast<std::ptrdiff_t>(lo));
}

// Ordena las posiciones 0..n-1 preguntando a Compare, con mergesort.
template <typename Compare>
std::vector<int> merge_order(int n, Compare is_less) {
    std::vector<int> order(static_cast<std::size_t>(n));
    std::iota(order.begin(), order.end(), 0);
    merge_range(order, 0, order.size(), is_less);
    return order;
}