#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include "partition.h"
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define ll long long
using namespace std;

vector<int> solve(vector<int> a) {
    int n = a.size();
    vector <pair<int, int>> v;
    for (int i = 0; i < n; i++) v.pb({a[i], i});
    sort(all(v));
    deque <int> res;
    int c = 1;
    res.pb(v[0].ss);
    vector <pair<int, int>> b;
    for (int i = 1; i < n; i++) {
        if (v[i].ff == v[i-1].ff) {
             if (c % 2) res.push_front(v[i].ss);
             else res.pb(v[i].ss);
             c++;
        }
        else {
            if (c % 2) {
                b.pb(v[i-1]);
            }
            c = 1;
            res.pb(v[i].ss);
        }
    }
    n = b.size();
    for (int i = 0; i < ceil(1. * n / 2) - 1; i++) {
        res.push_front(b[i].ss);
    }
    res.push_front(b.back().ss);
    for (int i = ceil(1. * n / 2) - 1; i < n-1; i++) {
        res.pb(b.back().ss);
    }
    vector <int> ans(all(res));
    return ans;
}
