early_order.cpp

#include <cstdint>
#include <iostream>
#include <vector>
#include <set>
#include <iterator>

using u32 = std::uint32_t;

void run(std::istream& stream);

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

    run(std::cin);

    return 0;
}

bool recursive_search(const std::vector<std::set<u32>>& positions, std::set<u32>& numbers, u32 pos,
                      std::vector<u32>& sequence) {
    if (numbers.empty())
        return true;

    std::set<u32>::iterator current = numbers.begin();
    while (current != numbers.end()) {
        auto node = numbers.extract(current);
        auto& set = positions[node.value()];
        auto exists = set.lower_bound(pos);
        if (exists != set.end() && recursive_search(positions, numbers, *exists, sequence)) {
            sequence.push_back(node.value());
            return true;
        }
        current = std::next(numbers.insert(std::move(node)).position);
    }
    return false;
}

void run(std::istream& stream) {
    u32 n{}, k{};
    stream >> n >> k;
    std::vector<std::set<u32>> positions(k + 1);
    std::set<u32> numbers;
    std::vector<u32> sequence;
    sequence.reserve(k);

    for (u32 i = 1; i <= k; ++i) {
        numbers.emplace_hint(numbers.end(), i);
    }
    for (u32 i = 0; i < n; ++i) {
        u32 num{};
        stream >> num;
        auto& set = positions[num];
        set.emplace_hint(set.end(), i);
    }

    recursive_search(positions, numbers, 0, sequence);
    std::copy(sequence.rbegin(), sequence.rend(), std::ostream_iterator<u32>(std::cout, " "));
}