#include "partition.h"
#include "iostream"
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;


vector<int> solve(vector<int> A) {

 //   unordered_map <int, bool> meme;
    vector <pair <int, int>> AA(A.size());
    int64_t summ = 0;
    int64_t last = 0;
    bool issr = 1;
    for (size_t io = 0; io < A.size(); io++)
    {
        summ += A[io];
        AA[io] = { A[io],io };
        if (issr)
        {
            if (A[io] < last) issr = 0;
            last = A[io];
        }
    }
    if (!issr)
        sort(AA.begin(), AA.end(), [](const pair <int, int>& a, const pair <int, int>& b) { return a.first < b.first; });

    vector <int> aa, bb;
    aa.reserve(A.size());
    bb.reserve((A.size()-1) / 2);
    int64_t BalanseOfTheWorld = 0;
    int64_t Banan = AA.size() / 2; 
    int64_t Mango = Banan;

    if (issr) Banan = (Banan + (Banan%2)) / 2;
    for (size_t i = 0; i < AA.size(); i++)
    {
        if (i < Banan || i >= AA.size() - (Mango - Banan))
        BalanseOfTheWorld += AA[i].first;
    }
    summ += summ % 2;
    while (BalanseOfTheWorld < summ/2)
    {       Banan--;
        BalanseOfTheWorld -= AA[Banan].first;
       
        BalanseOfTheWorld += AA[A.size() - (Mango - Banan)].first;
    }

    for (size_t i = 0; i < AA.size(); i++)
    {
        if (i < Banan || i >= AA.size() -  (Mango - Banan)  )
            aa.push_back(AA[i].second);
        else
            bb.push_back(AA[i].second);

    }


  /*  for (size_t i = 0; i < Banan; i++)
    {
        aa.push_back(AA[i].second);
    }

    for (size_t i = 0; i < Mango - Banan; i++)
    {
        aa.push_back(AA[AA.size() - i - 1].second);
    }

    for (size_t i = Banan; i < AA.size() - (Mango - Banan); i++)
    {
        bb.push_back(AA[i].second);
    }*/

    for (size_t io = 0; io < A.size(); io++)   
    {
       /* auto i = AA[io].first;
   
        if (BalanseOfTheWorld > 0)
        {
            aa.push_back(AA[io].second);
            BalanseOfTheWorld -= i;
        }
        else
        {
            bb.push_back(AA[io].second);
            BalanseOfTheWorld += i;
        }*/

    }
    for (auto i : bb) aa.push_back(i);
    
    

    return aa;
}
