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

struct elem{
    int x, id;
    bool operator< (const elem& other) const{
        return x < other.x;
    }
}a[2000005];

int sp[2000005];

vector<int> solve(vector<int> v){
    int n = v.size();
    for(int i = 1; i <= n; i++){
        a[i] = {v[i - 1], i - 1};
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        sp[i] = sp[i - 1] + a[i].x;
    }
    sp[n + 1] = sp[n];
    int bestpref = 0, bestsuf = -1, best = n + 1;
    for(int i = 0; i <= n; i++){
        if(sp[i] >= sp[n] - sp[i]){
            //iau i ultimul
            if(abs(2 * i - n) < best){
                bestpref = i;
                bestsuf = n + 1;
                best = abs(2 * i - n);
            }
            break;
        }
        for(int j = n; j > i; j--){
            if(2 * (sp[i] + sp[n] - sp[j - 1]) >= sp[n] && 2 * (sp[i] + sp[n - 1] - sp[j - 1]) < sp[n]){
                if(abs(2 * (i + n - j + 1) - n) < best){
                    bestpref = i;
                    bestsuf = j;
                    best = abs(2 * (i + n - j + 1) - n);
                }
            }
        }
    }
    vector<int> ans;
    for(int i = 1; i <= bestpref; i++){
        ans.push_back(a[i].id);
    }
    for(int j = bestsuf; j <= n; j++){
        ans.push_back(a[j].id);
    }
    for(int i = bestpref + 1; i <= bestsuf - 1; i++){
        ans.push_back(a[i].id);
    }
    return ans;
}
