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

using namespace std;

vector<int> solve(vector<int> v){
    int n=v.size();
    vector<int> s;
    vector<int> o;
    s.resize(n+1);
    o.resize(n+1);

    for(int i=0;i<n;i++)o[v[i]]=i;
    sort(v.begin(), v.end());

    int idx1=0, idx2=n/2;if(n%2)idx2++;
    for(int i=0;i<n;i++){
        if(i%2==0)s[idx1++]=o[v[i]];
        else s[idx2++]=o[v[i]];
    }

    s.pop_back();

    return s;
}
