#include "partition.h"
#include<iostream>
#include<vector>
#include <math.h>
#include <algorithm>
#include <numeric>
std::vector<int> solve(std::vector<int> A) {
    int mx = 0;
    for (int i = 0 ; i < A.size(); i++) {
        mx = max(A[i], mx);
    }
    int sum = mx;
    std::vector<std::vector<int>> cp, cnt(sum+1);
    std::vector<int> path;
    for (int i = 0; i < A.size(); i++) {
        cnt[A[i]].push_back(i);
    }
    cp = cnt;

    for (int i = 0; i <= mx; i++) {
        int cntr = cnt[i].size();
        for (int j = 0; j < cp[i].size() / 2; j++) {
            path.push_back(cnt[i][cntr--]);
            cnt[i].pop_back();
        }
    }
    for (int i = 0; i <= mx; i++) {
        int cntr = cnt[i].size();
        for (int j = 0; j < cp[i].size() / 2; j++) {
            path.push_back(cnt[i][cntr--]);
            cnt[i].pop_back();
        }
    }

    return path;
}
