#include <bits/stdc++.h>
#define all(A) A.begin(), A.end()
using namespace std;

vector <int> solve(vector <int> A){
    int n = A.size();
    vector <pair <int, int>> v;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += A[i];
        v.push_back({A[i], i});
    }
    sort(all(v));
    int s = 0;
    deque <int> martina;
    deque <int> deni;
    int i = 0;
    while (s * 2 < sum && i < n / 2) {
        s += v[i].first;
        martina.push_back(v[i].second);
        i++;
    }
    for (; i < n; i++) {
        deni.push_back(v[i].second);
    }
    if (martina.size() < n / 2) {
        vector <int> ans;
        ///cout << 1 << endl;
        for (auto x : martina) ans.push_back(x);
        for (auto x : deni) ans.push_back(x);
        return ans;
    }
    for (int i = n - 1; i >= martina.size(); i--) {
        if (s * 2 >= sum) break;
        int x = martina.front();
        int y = deni.back();
        s -= v[x].first; s += v[y].first;
        martina.pop_front();
        martina.push_back(y);
        deni.pop_back();
        deni.push_front(x);
    }
    vector <int> ans;
    for (auto x : martina) ans.push_back(x);
    for (auto x : deni) ans.push_back(x);
    return ans;
}

