#include "partition.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> check(vector<pair<int,int>>& wut, vector<long long> pr, int y) {
    int n = wut.size()-1;
    long long s = pr[n];
    vector<int> ans(0);
    int x;
    for(int j = n-y+1; j >= 0; j--) {
        if((pr[j+y-1]-pr[y])*2 < s) {
            x = j;
            break;
        }
    }
    vector<bool> yo(n+1,true);
    for(int j = x+1; j <= x+y-1; j++) {
        ans.push_back(wut[j].second);
        yo[j] = false;
    }
    if(x == n-y+1) {
        ans.push_back(wut[x].second);
        yo[x] = false;
    }
    else {
        ans.push_back(wut[n].second);
        yo[n] = false;
    }
    for(int i = 1; i <= n; i++) {
        if(yo[i]) {
            ans.push_back(wut[i].second);
        }
    }
    return ans;
}

std::vector<int> solve(std::vector<int> a) {
    vector<int> ans1(0);
    vector<int> ans2(0);
    int n = a.size();
    int d1 = INT_MAX,d2 = INT_MAX;
    long long s = 0;
    vector<pair<int,int>> wut(1,{-1,-1});
    for(int i = 0; i < n; i++) {
        wut.push_back({a[i],i});
    }
    sort(wut.begin(),wut.end());
    vector<long long> pr(n+1);
    for(int i = 1; i <= n; i++) {
        pr[i] = pr[i-1]+wut[i].first;
    }
    s = pr[n];
    int l = n/2+1,r = n/2;
    int j = 0;
    while(true) {
        int z = 0;
        if(j%2 == 0) {
            l--;
            z = l;
        }
        else {
            r++;
            z = r;
        }
        if(pr[z-1]*2 < s && (pr[n]-pr[n-z])*2 >= s) {
            return check(wut,pr,z);
        }
        j++;
    }
}
