#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e6 + 5;
const int MAXPWR = 30;

int n;
pair<int, int> a[maxn];

vector<int> ans;
long long sum = 0;
vector<int> positions[maxn];
int toReal[maxn];
unordered_map<int, int> compressed;
vector<pair<int, int>> alone;
vector<long long> pref;

long long calcPrefSum(int from, int to)
{
    if (from == 0) return pref[to];
    return pref[to] - pref[from - 1];
}

void compress()
{
    int curr = 0;

    sort(a, a + n);

    for (int i = 0; i < n; ++i)
    {
        if (i == 0 || a[i].first != a[i - 1].first)
        {
            compressed[a[i].first] = ++curr;
            toReal[curr] = a[i].first;
        }
    }

    for (int i = 0; i < n; ++i)
    {
        a[i].first = compressed[a[i].first];
    }
}

int countNumbers[maxn];

std::vector<int> solve(std::vector<int> A)
{
    n = A.size();
    ans.resize(n);
    alone.clear();
    pref.clear();
    compressed.clear();
    sum = 0;

    if (n == 1) return {0};

    for (int i = 0; i < n; ++i)
    {
        a[i] = {A[i], i};
        ans[i] = 0;
    }

    compress();

    for (int i = 0; i < n; ++i)
    {
        positions[a[i].first].push_back(a[i].second);
    }

    int lPointer = 0, rPointer = n - 1;

    for (int i = 0; i < n; ++i)
    {
        if (positions[a[i].first].empty()) continue;

        if (positions[a[i].first].size() >= 2)
        {
            for (int j = 0; j + 2 <= positions[a[i].first].size(); j += 2)
            {
                //cout << "at " << lPointer << " " << positions[a[i]][j] << endl;
                ans[lPointer++] = positions[a[i].first][j];
                //cout << "at " << rPointer << " " << positions[a[i]][j + 1] << endl;
                ans[rPointer--] = positions[a[i].first][j + 1];
            }
        }

        if (int(positions[a[i].first].size()) % 2 == 1)
        {
            //cout << "add " << a[i] << " " << positions[a[i]].back() << endl;
            sum += toReal[a[i].first];
            countNumbers[a[i].first] = positions[a[i].first].back();
        }

        positions[a[i].first].clear();
    }

    for (int i = 0; i < maxn; ++i)
    {
        if (countNumbers[i] != 0)
        {
            alone.push_back({toReal[i], countNumbers[i]});
            countNumbers[i] = 0;
        }
    }

    if (alone.empty()) return ans;

    if (sum % 2 == 0) sum /= 2;
    else sum = sum / 2 + 1;

    int sz = int(alone.size());
    int targetSz = (sz % 2 == 0 ? sz / 2 : sz / 2 + 1);
    int best = alone.size();
    pair<int, int> bestPair;

    //for (int i = 0; i < alone.size(); ++i) cout << alone[i].first << " " << alone[i].second << endl;
    //cout << "now " << targetSz << " " << sum << endl;

    long long currSum = 0;

    for (int i = 0; i < sz; ++i)
    {
        currSum += alone[i].first;
        pref.push_back(currSum);
    }

    for (int i = 0; i < sz; ++i)
    {
        /*long long curr = 0;
        int to = -1;

        for (int j = i; j < sz; ++j)
        {
            curr += alone[j].first;
            if (curr >= sum)
            {
                to = j;
                break;
            }
        }

        if (to == -1) break;*/

        if (calcPrefSum(i, sz - 1) < sum) continue;

        int l = i, r = sz - 1;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (calcPrefSum(i, mid) >= sum)
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        //cout << "here " << i << " " << l << endl;

        int len = l - i + 1;
        if (best > abs(targetSz - len))
        {
            best = abs(targetSz - len);
            bestPair = {i, l};
        }
    }

    //cout << "now " << bestPair.first << " " << bestPair.second << endl;

    for (int i = bestPair.first; i <= bestPair.second; ++i)
    {
        ans[lPointer++] = alone[i].second;
    }

    for (int i = 0; i < alone.size(); ++i)
    {
        if (bestPair.first <= i && i <= bestPair.second) continue;
        ans[lPointer++] = alone[i].second;
    }

    return ans;
}
