#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
const int MAXN = 2000000;///
vector<int> vrez;
struct nume {
    int val, poz;
} v[MAXN];
char cmp(nume a, nume b) {
    return a.val < b.val;
}
std::vector<int> solve(std::vector<int> A) {
    //resetez vectorii

    //pun mai intai cele mai mici (n + 1) / 2 - 1
    //si dupa prima parte e clar < s / 2
    int i, n, p, p2, j;
    long long sum, jum, s;
    n = A.size();
    sum = 0;
    for (i = 0; i < n; i++) {
        v[i].val = A[i];
        v[i].poz = i;
        sum += A[i];
    }
    jum = (sum + 1) / 2;
    //daca impart in x, n - x sa fie s(x) < jum si s(x + 1) >= jum si s(x) este suma pe prefixul 0...i
    p = (n + 1) / 2;//primii p cei mai mici ii pun
    //nth_element(v, v + p - 1, v + n, cmp);
    vrez.clear();
    if (n == 1) {
        vrez.push_back(0);
    } else if (n == 2) {
        //mai intai maximul ca sa fie dif = 0
        for (i = 1; i >= 0; i--) {
            vrez.push_back(v[i].poz);
        }
    } else if (v[0].val == v[n - 1].val) {///
        for (i = 0; i < n; i++) {
            vrez.push_back(i);
        }
    } else {
        //fara al p-lea sa aiba suma < jum si dupa cu el sa fie > jum
        s = 0;
        for (i = 0; i < n; i++) {
            if (i < p) {
                s += v[i].val;
                vrez.push_back(v[p - i - 1].poz);
            } else {
                vrez.push_back(v[i].poz);
            }
        }
        //primele p - 1 au sigur suma < jum
        //il inlocuiesc pe ultimul cu maximul
        j = n - 1;
        p2 = p - 2;
        while (s < jum) {
            //pe pozitia p il pun pe maximul ramas j
            //si daca suma este < jum atunci dau swap la p cu p2
            s += A[vrez[j]] - A[vrez[p - 1]];//alea sunt pozitiile din vectorul original
            swap(vrez[j], vrez[p - 1]);
            j--;
            if (j == p - 1) {
                j = n - 1;
            }
            if (s < jum) {
                swap(vrez[p - 1], vrez[p2]);
                p2--;
            }
        }
    }
    return vrez;
}
