#include "partition.h"
#include<algorithm>
#include<set>
using namespace std;

std::vector<int> solve(std::vector<int> A) {
    vector<pair<int, int>> index_paired;

    index_paired.reserve(200000);

    int p_cnt = (A.size()/2)/2;

    for(int i = 0; i < A.size(); i++) {
        index_paired.push_back({A[i], i});
    }


    sort(index_paired.begin(), index_paired.end());


    vector<int> indices;
    for(int i = 0; i < p_cnt; i++) {
        indices.push_back(index_paired[i].second);
        indices.push_back(index_paired[A.size()-1-i].second);
    }
    if(A.size() % 2) {
        indices.push_back(index_paired[A.size()-1-p_cnt].second);
    }
    for(int i = p_cnt; indices.size() < A.size(); i++) {
        indices.push_back(index_paired[i].second);
    }
    return indices;
}

