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

using namespace std;


std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    if(n == 1) {
        return {0};
    }
    int Ans = 1e9;
    vector<int>ans;
    vector<pair<int,int>> V;
    for(int i=0; i<n; i++) V.push_back({A[i], i});
    sort(V.begin(), V.end());
    long long sum=0;
    int biggest=0;
    for(int i=0; i<n; i++) sum+=A[i];
    for(int i=n-1; i>=0; i--) {
        if(V[i].first == V[n-1].first) biggest++;
        else break;
    }

    vector<long long>pref(n,0);
    for(int i=0; i<n; i++) {
        pref[i] = V[i].first;
        if(i) pref[i] += pref[i-1];
    }

    for(int i=(n+1)/2; i>=-1; i--) {
        long long tmp=0;
        int tmp1=0;
        if(i >= 0) {
            tmp = pref[i];
            tmp1 = i+1;
        }
        tmp = (sum+1)/2 - tmp; // KOLIKO MI FALI?
        int tmp2 = (tmp+V[n-1].first-1) / V[n-1].first;
        if(tmp2 > biggest) break;
        //cout << "i-" << i << " tmp-" << tmp << " tmp2-" << tmp2 << endl;
        if(abs((tmp1+tmp2) - (n-tmp1-tmp2)) < Ans) {
            Ans = abs((tmp1+tmp2) - (n-tmp1+tmp2));
            vector<int> v;
            vector<int>visited(n,0);
            for(int j=0; j<tmp1; j++) {
                v.push_back(V[j].second);
                visited[V[j].second] = 1;
            }
            for(int j=0; j<=tmp2; j++) {
                v.push_back(V[n-1-j].second);
                visited[V[n-1-j].second] = 1;
            }
            for(int j=0; j<n; j++) {
                if(!visited[j]) v.push_back(j);
            }
            ans = v;
        }
    }
    return ans;
}
