/// NEKADA DAVNO BIO JEDAN VITEZ IZ ZAMKA...
#include<bits/stdc++.h>
#define ll long long
#include "partition.h"
using namespace std;
vector<int> solve(std::vector<int> A) {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n = A.size();
    vector<ll> p(n + 1);
    unordered_map<int, vector<int>> m;
    for (int i = 0; i < n; i++){
        m[A[i]].push_back(i);
    }
    sort(A.begin(), A.end());
    ll s = 0;
    for (int i = n - 1; i >= 0; i--){
        p[i] = A[i] + p[i + 1];
        s += A[i];
    }
    sort(p.begin(), p.end());
    s += s % 2;
    s /= 2;
    ll cur = 0, po = 0, k = 0;
    //for (auto el : p)cout << el << " ";
    while (po <= n){
        int it = lower_bound(p.begin(), p.end(), s - cur) - p.begin();
        //cout << po << " " << it << "\n";
        //cout << s << "\n";
        if (n % 2 == 1){
            if (it + po == n / 2 || it + po == n / 2 + 1){
                k = it;
                break;
            }
        }
        else{
            if (it + po == n / 2){
                k = it;
                break;
            }
        }
        cur += A[po];
        po++;
        //cout << "v";
    }
    k = n - 1 - k;
    vector<int> sol;
    for (int i = 0; i < po; i++){
        if (m[A[i]].size() > 0){
            sol.push_back(m[A[i]][m[A[i]].size() - 1]);
            m[A[i]].pop_back();
        }
    }
    for (int i = n - 1; i > k; i--){
        if (m[A[i]].size() > 0){
            sol.push_back(m[A[i]][m[A[i]].size() - 1]);
            m[A[i]].pop_back();
        }
    }
    for (int i = 0; i < n; i++){
        if (m[A[i]].size() > 0){
            sol.push_back(m[A[i]][m[A[i]].size() - 1]);
            m[A[i]].pop_back();
        }
    }
    return {sol};
}

/*
1
9
5 6 6 3 1 1 4 4 3
*/
/*
1
5
1 1 1 1 1
*/
///...VITEZ RAZMISLJA DA SE OBESI...
