#include "partition.h"
#include <bits/stdc++.h>
#define abs(x) ((x) < 0 ? -(x) : (x))
#define mkp make_pair
#define int long long

using namespace std;

int n, sum;
vector<int> v, perm;
vector<signed> best;
int score;
mt19937 mt(67676767);

void tryThis(deque<int> vec) {
    int s = 0;
    for(int i=0; i<n; ++i) {
        s += v[vec[i]];
        if(s >= (sum + 1) / 2) {
            if(abs(i + 1 - (n - i - 1)) < score) {
                score = abs(i + 1 - (n - i - 1));
                best.resize(n);
                for(int i=0; i<n; ++i) {
                    best[i] = perm[vec[i]];
                }
            }
            return;
        }
    }
}

vector<signed> solve(vector<signed> _v) {
    n = _v.size();
    if(n == 1) {
        return {0};
    }
    v.resize(n);
    for(int i=0; i<n; ++i) {
        v[i] = _v[i];
    }
    perm.assign(n, 0);
    for(int i=0; i<n; ++i) {
        perm[i] = i;
    }
    score = n;
    sum = 0;
    for(int i=0; i<n; ++i) {
        sum += v[i];
    }
    sort(perm.begin(), perm.end(), [](int a, int b){return v[a] < v[b];});
    sort(v.begin(), v.end());
    vector<int> l, r;
    vector<int> rem = {0};
    int ok = 0;
    for(int i=1; i<n; ++i) {
        if(v[i] == v[i-1] && !ok) {
            l.push_back(i-1);
            r.push_back(i);
            rem.pop_back();
            ok = 1;
        } else {
            rem.push_back(i);
            ok = 0;
        }
    }
    if(!rem.empty()) {
        int maxi = 0;
        for(int i=1; i<rem.size(); ++i) {
            if(v[rem[i]] > v[rem[maxi]]) {
                i = maxi;
            }
        }
        swap(rem[maxi], rem[rem.size() / 2]);
    }
    best.clear();
    for(int i=0; i<l.size(); ++i) {
        best.push_back(perm[l[i]]);
    }
    for(int i=0; i<rem.size(); ++i) {
        best.push_back(perm[rem[i]]);
    }
    for(int i=0; i<r.size(); ++i) {
        best.push_back(perm[r[i]]);
    }
    return best;
}
