#include "partition.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> solve(vector<int> A) {
    int n = A.size();
    vector<pair<int, int>> so;
    for (int i = 0; i < n; i++){
        so.push_back({A[i], i});
    }
    sort(so.begin(), so.end());
    vector<int> ans, us(n + 1, 0), de;
    for (int i = 0; i < n; i++){
        if (!de.empty() && A[de.back()] == so[i].first){
            ans.push_back(de.back());
            us[de.back()] = 1;
            de.pop_back();
        }
        else{
            de.push_back(so[i].second);
        }
    }
    ll su = 0, go = 0, cnt = 0, sz = 0;
    for (int i = 0; i < de.size(); i++){
        cnt++, su += A[de[i]];
    }
    go = (su + 1) / 2, sz = (cnt + 1) / 2;
    ll cur = 0, l = 0, r = sz - 1;
    for (int i = 0; i < sz; i++){
        cur += A[de[i]];
    }
    while (r < de.size() && cur < go){
        l++, r++;
        cur = cur + A[de[r]] - A[de[l - 1]];
    }
    for (int i = l; i <= r; i++){
        ans.push_back(de[i]);
        us[de[i]] = 1;
    }
    for (int i = 0; i < n; i++){
        if (us[i] == 0) ans.push_back(i);
    }
    return ans;
}
