#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int n;
pair<int, int> a[maxn];

std::vector<int> solve(std::vector<int> A)
{
    n = A.size();
    for (int i = 0; i < n; ++i)
    {
        a[i + 1] = {A[i], i};
    }

    vector<int> ans(n);
    int l = 0, r = n - 1;

    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; ++i)
    {
        int nxt = n;

        for (int j = i + 1; j <= n; ++j)
        {
            if (a[j].first != a[i].first)
            {
                nxt = j - 1;
                break;
            }
        }

        for (int j = i; j <= nxt; j += 2)
        {
            ans[l++] = a[j].second;
            ans[r--] = a[j + 1].second;
        }

        i = nxt;
    }

    return ans;
}
