#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> vecglob;

bool comp(int a, int b)
{
    return vecglob[a] < vecglob[b];
}

vector<int> solve(std::vector<int> vec)
{
    vecglob = vec;
    vector<int> res;
    ll amount = (ll)vec.size();
    ll best = LLONG_MAX, bestmask, tots = 0;
    bool powers = true;
    for(ll num : vec)
    {
        if(__builtin_clzll(num) + __builtin_ctzll(num) + 1 != 64) powers = false;
        tots += num;
    }
    // cout << powers;
    // if(amount <= 20)
    // {
    //     for(ll mask = 0; mask <= (1ll << (amount+1))-1; mask++)
    //     {
    //         ll s = 0, am = 0, big = 0;
    //         for(ll i = 0; i < amount; i++)
    //         {
    //             if(mask & (1ll << i))
    //             {
    //                 am++;
    //                 s += vec[i];
    //                 big = max(big, (ll)vec[i]);
    //             }
    //         }
    //         if(s-big < (tots+1)/2) continue;
    //         if(abs(am - amount - am) < best)
    //         {
    //             best = abs(am - amount - am);
    //             bestmask = mask;
    //         }
    //     }
    //     for(ll i = 0; i < amount; i++)
    //     {
    //         if(bestmask & (1ll << i)) res.push_back(i);
    //     }
    //     sort(res.begin(), res.end(), comp);
    //     for(ll i = 0; i < amount; i++)
    //     {
    //         if(!(bestmask & (1ll << i))) res.push_back(i);
    //     }
    // }
    // else if(powers)
    // {

    // }
    vector<pair<int, int>> vec2;
    for(ll i = 0; i < amount; i++)
    {
        vec2.push_back({vec[i], i});
    }
    sort(vec2.begin(), vec2.end());
    for(ll i = 0; i < amount; i += 2)
    {
        res.push_back(vec2[i].second);
    }
    for(ll i = 1; i < amount; i += 2)
    {
        res.push_back(vec2[i].second);
    }
    return res;
}