#include "partition.h"
#include <bits/stdc++.h>
using namespace std;


// #define ll long long 

std::vector<int> solve(std::vector<int> b) {
    
    vector <pair<int,int>> a;

    int n = b.size();
    unordered_map<int,int> cnt;
    for (auto x:b) {
        cnt[x]++;
    }


    int cur = 0;
    int mx = -1e9;
    for (auto [key,val]:cnt) {
        if (val%2==0) continue;
        mx = max(mx,key);
    }


    cnt[mx]--;
    for (auto [key,val]:cnt) {
        if (key < 0) continue;
        cur += (val%2);
    }
    int l = (cur/2);
    int r = (cur+1)/2;
    for (auto [key,val]:cnt) {
        if (key < 0) continue;
        int res = val%2;
        cnt[key]/=2;
        if (l && res) cnt[key]++,l--;
    }
    cnt[mx]++;
    vector <int> fix(n+1,0);
    vector <int> ans;
    for (int i = 0; i < n; i++) {
        if (cnt[b[i]]) {
            cnt[b[i]]--;
            ans.emplace_back(i);
            fix[i] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (!fix[i]) {
            ans.emplace_back(i);
        }
    }

    return ans;

    
    
}
