#include "partition.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <deque>
#include <math.h>
#include <array>
#include <set>
#include <string>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

const ll INF = 1e18;

vector<int> solve(vector<int> A) {
    ll n = A.size();
    vpll arr(n);
    double sum = 0;
    vll pref(n);
    rep(i, 0, n) {
        arr[i] = { A[i], i };
        sum += (double)A[i];
        pref[i] = A[i];
        if (i > 0) pref[i] += pref[i - 1];
    }
    sort(A.begin(), A.end());
    sort(arr.begin(), arr.end());
    sum /= 2;
    ll cur_sz = 0, cur_sum = 0;
    multiset<pll> idx;
    rep(i, 0, n) {
        if (cur_sum >= sum) {
            break;
        }
        if (cur_sz >= (n-1) / 2) {
            cur_sum -= (*idx.begin()).first;
            idx.erase(idx.begin());
            cur_sum += A[i];
            idx.insert(arr[i]);
            continue;
        }
        cur_sz++;
        cur_sum += A[i];
        idx.insert(arr[i]);
    }
    vector<int> ans(n);
    ll pos = 0;
    for (auto& it : idx) {
        ans[pos] = it.second;
        pos++;
    }
    rep(i, 0, n) {
        auto it = idx.lower_bound({ A[i], -1 });
        if (it != idx.end() && (*it).first == A[i]) {
            idx.erase(it);
            continue;
        }
        ans[pos] = arr[i].second;
        pos++;
    }
    return ans;


    /*
    ll f = 0, t = n, mid;
    ll res = 0;
    while (f <= t) {
        mid = (f + t) / 2;
        ll num_pref = (n - 2 - mid) / 2;
        ll num_suf = (n - 2 - mid + 1) / 2;
        ll cur_sum_pref = pref[num_pref];
        ll cur_sum_suf = pref[n - 1] - pref[n - num_suf - 1];
        if (cur_sum_pref <= sum && cur_sum_suf >= sum) {
            res = ;
            t = mid - 1;
        }
        else {
            f = mid + 1;
        }
    }

    return ans;*/
}
