#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<functional>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<queue>
#include<bit>

using namespace std;
//#define int long long
#define pii pair<int, int>
#define ll long long
#define ull unsigned ll
#define pll pair<ll, ll>
#define ve vector
#define vi ve<int>
#define vvi ve<vi>
#define vll ve<ll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a= max(a, b)
#define all(a) a.begin(), a.end()
#define for0(i, n) for(int i= 0; i < n; ++i)

extern vector<int> solve(vector<int> A) {
    int n = A.size();
    vi a(n); iota(all(a), 0ll);
    sort(all(a), [&](int i, int j) {
        return A[i] < A[j];
        });
    vi ans; ans.reserve(n);
    vi b;
    int i = 0;
    while(i < n){
        if (i + 1 < n && A[a[i]] == A[a[i + 1]]) {
            ans.push_back(a[i]);  ++i;
        }
        else b.push_back(a[i]);
        ++i;
    }
    for (int j = 0; j < (int)b.size() - 1; ++j) {
        if (j == (b.size() - 1) / 2) ans.push_back(b.back());
        ans.push_back(b[j]);
    }
    if (b.size() == 1) ans.push_back(b.back());
    i = 0;
    while(i < n) {
        if (i + 1 < n && A[a[i]] == A[a[i + 1]]) {
            ans.push_back(a[i + 1]);  ++i;
        }
        ++i;
    }
    return ans;
}