#include "partition.h"

#include <bits/stdc++.h>

using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();

    vector <int> p(n);

    iota(begin(p), end(p), 0);
    sort(begin(p), end(p), [&](int &i, int &j){
         return A[i] < A[j];
    });

    long long S = accumulate(begin(A), end(A), 0LL);

    S = (S + 1) / 2;

    vector <long long> pf(n + 1);

    for ( int i = 0; i < n; i++ ) pf[i + 1] = pf[i] + A[p[i]];

    int l = -1, r = 0;

    for ( int i = 1, j = 0; i <= n; i++ ){
        if ( pf[i] < S ) continue;

        while ( pf[i] - pf[j] >= S ) j++;

        if ( l == -1 || abs(n - 2 * (r - l + 1)) > abs(n - 2 * (i - j + 1)) ){
            l = j, r = i;
        }
    }

    vector <int> ans;

    for ( int i = l; i <= r; i++ ) ans.push_back(p[i - 1]);

    for ( int i = 1; i <= n; i++ ){
        if ( i < l || i > r ) ans.push_back(p[i - 1]);
    }

//    long long sum = accumulate(begin(A), end(A), 0LL), cnt = 0;
//
//    for ( auto &u: ans ){
//        if ( cnt < (sum + 1) / 2 ){
//            cnt += A[u];
//        } else break;
//    }
//
//    cout << "! " << cnt * 2 - sum << ' ';

    return ans;
}
