#include <algorithm> #include <cstdlib> #include <iostream> #include <set> #include <tuple> #include <vector> using namespace std; using i64 = long long; struct FreqFirst { bool operator()(tuple<int, int, int> lhs, tuple<int, int, int> rhs) const { get<1>(lhs) *= -1; get<1>(rhs) *= -1; return lhs > rhs; } }; struct IdxFirst { bool operator()(tuple<int, int, int> lhs, tuple<int, int, int> rhs) const { return get<1>(lhs) < get<1>(rhs); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; vector<int> A(N + 1); vector<vector<int>> idxs(N + 1); for (int i = 1; i <= N; ++i) { cin >> A[i]; idxs[A[i]].push_back(i); } for (auto& idx : idxs) { if (!idx.empty()) reverse(idx.begin(), idx.end()); } set<tuple<int, int, int>, FreqFirst> freq_set; // (frequency, first appearance, value) set<tuple<int, int, int>, IdxFirst> idx_set; // (frequency, first appearance, value) auto pop = [&](int lst_val) { for (const auto& elem : idx_set) { if (get<2>(elem) != lst_val) return get<1>(elem); } cout << "-1\n"; exit(0); }; for (int i = 1; i <= N; ++i) { if (!idxs[i].empty()) { freq_set.emplace(idxs[i].size(), idxs[i].back(), i); idx_set.emplace(idxs[i].size(), idxs[i].back(), i); } } vector<int> ans(N + 1); for (int i = 1; i <= N; ++i) { int cand = pop(A[ans[i - 1]]), val = A[cand]; auto now = make_tuple(idxs[val].size(), cand, val); freq_set.erase(now); idx_set.erase(now); if (get<0>(*freq_set.begin()) <= (N - i + 1) >> 1) { int freq = get<0>(now), idx = get<1>(now), num = get<2>(now); ans[i] = cand; idxs[val].pop_back(); if (freq > 1) { idx = idxs[num].back(); freq_set.emplace(freq - 1, idx, num); idx_set.emplace(freq - 1, idx, num); } } else { freq_set.insert(now); idx_set.insert(now); auto itr = freq_set.begin(); int freq = get<0>(*itr), idx = get<1>(*itr), num = get<2>(*itr); idx_set.erase(*itr); freq_set.erase(itr); ans[i] = idx; idxs[num].pop_back(); if (freq > 1) { idx = idxs[num].back(); freq_set.insert(make_tuple(freq - 1, idx, num)); idx_set.insert(make_tuple(freq - 1, idx, num)); } } } for (int i = 2; i <= N; ++i) { if (A[ans[i]] == A[ans[i - 1]]) { cout << "-1\n"; return 0; } } for (int i = 1; i <= N; ++i) cout << ans[i] << ' '; return 0; }