#include "partition.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>

struct Element
{
    int val;
    int idx;
};

std::vector<Element> a;
std::vector<int> perm;
std::vector<int> permL;
std::vector<int> permR;

std::vector<int> solve(std::vector<int> A)
{
    for(int i = 0 ; i < A.size() ; ++i)
    {
        a.push_back({A[i], i});
    }

    std::sort(a.begin(), a.end(), [&](const Element &left, const Element &right)
    {
        return left.val < right.val;
    });

    
    for(int i = 0 ; i < a.size() ; i += 2)
    {
        perm.push_back(a[i].idx);
    }

    for(int i = 1 ; i < a.size() ; i += 2)
    {
        perm.push_back(a[i].idx);
    }

    return perm;
}
