#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 offs1=n/4, offs2=n-1-(n/2-offs1);

    int sIdx=0;

    for(int i=0;i<offs1;i++)
        s[sIdx++]=o[v[i]]+1;
    for(int i=offs2+1;i<n;i++)
        s[sIdx++]=o[v[i]]+1;
    for(int i=offs1;i<=offs2;i++)
        s[sIdx++]=o[v[i]]+1;

    s.pop_back();

    return s;
}
