#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> solve(vector<int> a) {
    int n = a.size();
    vector<pair<int, int>> aa(n);
    for (int i = 0; i < n; i++)
    {
        aa[i] = {a[i], i};
    }
    sort(aa.begin(), aa.end());
    ll Sum = 0;
    for (int i = 0; i < n; i++)
    {
        Sum += aa[i].first;
    }

    if (n % 2 == 0)
    {
        ll cntr = n / 2 - 1;

        ll SumNow = 0;
        for (ll i = 0; i < n; i++)
        {
            if ((SumNow + aa[cntr-i].first) * 2 >= Sum)
            {
                vector<int> ans;
                unordered_set<int> st;
                for (ll j = cntr-i; j <= cntr+i; j++)
                {
                    ans.push_back(aa[j].second);
                    st.insert(aa[j].second);
                }
                for (ll j = 0; j < n; j++)
                {
                    if (st.find(aa[j].second) == st.end())
                    {
                        ans.push_back(aa[j].second);
                    }
                }
                return ans;
            }
            SumNow += aa[cntr-i].first;
            if ((SumNow + aa[cntr+i+1].first) * 2 >= Sum)
            {
                vector<int> ans;
                unordered_set<int> st;
                for (ll j = cntr-i; j <= cntr+i+1; j++)
                {
                    ans.push_back(aa[j].second);
                    st.insert(aa[j].second);
                }
                for (ll j = 0; j < n; j++)
                {
                    if (st.find(aa[j].second) == st.end())
                    {
                        ans.push_back(aa[j].second);
                    }
                }
                return ans;
            }
            SumNow += aa[cntr+i+1].first;
        }
    }
    else
    {
        ll cntr = n / 2;

        ll SumNow = 0;
        for (ll i = 0; i < n; i++)
        {
            if ((SumNow + aa[cntr-i].first) * 2 >= Sum)
            {
                vector<int> ans;
                unordered_set<int> st;
                for (ll j = cntr-i; j <= cntr+i; j++)
                {
                    ans.push_back(aa[j].second);
                    st.insert(aa[j].second);
                }
                for (ll j = 0; j < n; j++)
                {
                    if (st.find(aa[j].second) == st.end())
                    {
                        ans.push_back(aa[j].second);
                    }
                }
                return ans;
            }
            SumNow += aa[cntr-i].first;
            if (i==0)continue;
            if ((SumNow + aa[cntr+i].first) * 2 >= Sum)
            {
                vector<int> ans;
                unordered_set<int> st;
                for (ll j = cntr-i; j <= cntr+i; j++)
                {
                    ans.push_back(aa[j].second);
                    st.insert(aa[j].second);
                }
                for (ll j = 0; j < n; j++)
                {
                    if (st.find(aa[j].second) == st.end())
                    {
                        ans.push_back(aa[j].second);
                    }
                }
                return ans;
            }
            SumNow += aa[cntr+i].first;
        }
    }
}
