#include "partition.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

std::vector<int> solve(std::vector<int> A){
    vector <pair<int, int>> v;
    map <int, int> mep;
    int impare = 0;
    for (int i = 0; i < A.size(); i++){
        v.push_back({A[i], i});
        mep[A[i]]++;
        if (mep[A[i]] == 1){
            impare++;
        }
        else{
            impare--;
        }
    }
    sort(v.begin(), v.end());
    vector <int> rez;
    if (impare == 0){
        //task 1
        for (int i = 0; i < v.size(); i += 2){
            rez.push_back(v[i].second);
        }
        for (int i = 1; i < v.size(); i += 2){
            rez.push_back(v[i].second);
        }
        return rez;
    }
    //task 2
    int N = v.size();
    for (int i = 0; i < N / 2; i++){
        rez.push_back(v[i].second);
    }
    rez.push_back(v.back().second);
    for (int i = N / 2; i + 1 < v.size(); i++){
        rez.push_back(v[i].second);
    }
    return rez;
}

