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

#define MAXN 2000000


vector<int> solve(vector<int> A){
  int n=A.size(),i;
  int x=(n+1)/2;
  long long S=0;
  vector<int> ind(n);

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

  sort(ind.begin(),ind.end(),[&](int a,int b){
    return A[a]<A[b];
  });

  vector<int> parts[2];

  i=0;
  while(i<n){
    int val=A[ind[i]];
    int p=0;
    do{
      parts[p].push_back(ind[i]);
      p=1-p;
      i++;
    }while(i<n&&A[ind[i]]==val);
  }

  for(int pos:parts[1]){
    parts[0].push_back(pos);
  }

  return parts[0];
}