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

#define MAXN 2000000

int ind[MAXN];

vector<int> solve(vector<int> A){
  int n=A.size();
  int i;
  vector<int> sol;

  for(i=0;i<n;i++){
    ind[i]=i;
  }

  sort(ind,ind+n,[&](int a,int b){
    return A[a]<A[b];
  });

  for(i=0;i<(n+1)/2-1;i++){
    sol.push_back(ind[i]);
  }
  sol.push_back(ind[n-1]);
  for(i=(n+1)/2-1;i<n-1;i++){
    sol.push_back(ind[i]);
  }

  return sol;
}