#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;


int n;
array<int,2> a[MAXN];

std::vector<int> solve(std::vector<int> A){
    n = A.size();
    long long sum = 0ll;
    for(int i = 0; i < n; ++i){
        a[i] = {A[i],i};
        sum += A[i];
    }
    sort(a, a+n);
    int sz = (n+1)/2, idx = 0;
    long long tmp = 0ll;
    for(int i = 0; i < sz; ++i) tmp += a[i][0];
    while(tmp < (sum+1)/2){
        tmp += a[idx+sz][0] - a[idx][0];
        ++idx;
    }
    /*for(int i = 0; i < (n+1)/2; ++i){
        tmp += a[i][0];
    }
    for(int i = 1;; ++i){
        if(tmp >= (sum+1)/2) break;
        else{
            tmp += a[n-i][0] - a[(n+1)/2-i][0];
            swap(a[(n+1)/2-i], a[n-i]);
        }
    }*/
    vector<int> r;
    for(int i = idx; i < idx+sz; ++i) r.push_back(a[i][1]);
    for(int i = 0; i < idx; ++i) r.push_back(a[i][1]);
    for(int i = idx+sz; i < n; ++i) r.push_back(a[i][1]);
    return r;
}
