#include #define REP_(i, a_, b_, a, b, ...) \ for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using i64 = long long; #include using i128 = boost::multiprecision::int128_t; using Int = boost::multiprecision::cpp_int; template inline bool chmax(T &a, U b) { return a < b and ((a = std::move(b)), true); } template inline bool chmin(T &a, U b) { return a > b and ((a = std::move(b)), true); } template inline int ssize(const T &a) { return (int)std::size(a); } template std::istream &operator>>(std::istream &is, std::vector &a) { for (auto &x : a) is >> x; return is; } template std::ostream &operator<<(std::ostream &os, const std::pair &a) { return os << "(" << a.first << ", " << a.second << ")"; } template std::ostream &print_seq(const Container &a, std::string_view sep = " ", std::string_view ends = "\n", std::ostream &os = std::cout) { auto b = std::begin(a), e = std::end(a); for (auto it = std::begin(a); it != e; ++it) { if (it != b) os << sep; os << *it; } return os << ends; } template struct is_iterable : std::false_type {}; template struct is_iterable())), decltype(std::end(std::declval()))>> : std::true_type {}; template ::value && !std::is_same::value && !std::is_same::value>> std::ostream &operator<<(std::ostream &os, const T &a) { return print_seq(a, ", ", "", (os << "{")) << "}"; } #ifdef ENABLE_DEBUG #include "debug_dump.hpp" #else #define DUMP(...) #endif using namespace std; struct UnionFind { int n; mutable std::vector parent; // positive: parent, negative: size int num_roots; explicit UnionFind(int sz) : n(sz), parent(sz, -1), num_roots(sz) {} bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (-parent[x] < -parent[y]) std::swap(x, y); parent[x] += parent[y]; parent[y] = x; --num_roots; return true; } int find(int v) const { if (parent[v] < 0) return v; return parent[v] = find(parent[v]); } int size(int v) const { return -parent[find(v)]; } bool same(int x, int y) const { return find(x) == find(y); } std::vector roots() const { std::vector res; res.reserve(num_roots); for (int i = 0; i < n; ++i) { if (parent[i] < 0) res.push_back(i); } return res; } }; vector solve() { int n; cin >> n; vector a(n); REP(i, n) cin >> a[i]; if (n == 2) { vector ans = {1, 2, 1}; return ans; } vector ix(n); REP(i, n) ix[i] = i; sort(ALL(ix), [&](int i, int j) { return a[i] < a[j]; }); priority_queue> pq; for (int i = n - 1; i > 0; --i) { int j = ix[i]; int k = ix[i - 1]; pq.emplace(a[j] * a[k], i, i - 1); } UnionFind uf(n); map> visited; int count = 0; while (pq.size() and count < n) { auto [prod, i, j] = pq.top(); pq.pop(); int vi = ix[i]; int vj = ix[j]; if (ssize(visited[vi]) >= 2 or ssize(visited[vj]) >= 2) { continue; } if (count != n - 1 and uf.same(vi, vj)) continue; uf.unite(vi, vj); ++count; visited[vi].push_back(vj); visited[vj].push_back(vi); DUMP(count, vi, vj, visited); if (j > 0) { Int ak = a[ix[j - 1]]; pq.emplace(a[vi] * ak, i, j - 1); } } int cur = 0; vector ans; ans.push_back(1); set done; while (ssize(done) < n) { for (auto x : visited[cur]) { if (done.count(x)) continue; ans.push_back(x + 1); cur = x; done.insert(cur); } } return ans; } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); print_seq(solve()); }