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

using namespace std;

const int MAXN = 2e6;
const int MAX = 33'554'432;
//map<int, int> f;
int f[MAX + 1];
vector<int> pos[MAX + 1];

struct date {
    int val, id;
};

date a[MAXN + 1];

bool by_val( date a, date b ) {
    return a.val < b.val;
}

std::vector<int> solve(std::vector<int> v) {
    int n = v.size();
    vector<int> rez;
    int i;
    for( i = 0; i < n; i++ ) {
        f[v[i]]++;
        pos[v[i]].push_back( i );
    }

    //sortarea:
    int m = 0;
    for( i = 1; i <= MAX; i++ ) {
        int cnt = 0;
        while( f[i] > 0 ) {
            a[m++] = { i, pos[i][cnt++] };
            f[i]--;
        }
    }

    if( n % 2 == 1 ) {
        for( i = 0; i < m; i += 2 )
            rez.push_back( a[i].id );
        for( i = 1; i < m; i += 2 )
            rez.push_back( a[i].id );
    } else {
        for( i = 1; i < m; i += 2 )
            rez.push_back( a[i].id );
        for( i = 0; i < m; i += 2 )
            rez.push_back( a[i].id );
    }
    return rez;
}

