#pragma GCC optimize("O3")
#include "partition.h"
#include "algorithm"
#include "iostream"

std::vector<int> solve(std::vector<int> A) {
    if (A.size() == 1) return {0};
    int n = A.size();
    std::vector<int>B(n);
    for(int i = 0; i < n; i ++)
        B[i] = i;
    sort(begin(B),end(B),[&A](int i,int j){return A[i]<A[j];});
    long long sm = 0;
    for (int i : A)
        sm += i;
    long long smA = A[B[0]], bs = 0;
    for(int i = 1;i<n/2;i++){
        if(smA - A[B[i]-1] > sm / 2)
            break;
        smA += A[B[i]],bs=i;
    }
    int i=bs+1;
    for(int j=i;j<n;j++){
        smA-=A[B[j-i]];
        smA+=A[B[j]];
        if(smA>sm/2){
            std::vector<int>ans;
            for(int k=j-i+1;k<=j;k++)
                ans.push_back(B[k]);
            for(int k=0;k<=j-i;k++)
                ans.push_back(B[k]);
            for(int k=j+1;k<n;k++)
                ans.push_back(B[k]);
            return ans;
        }
    }
    std::vector<int>ans;
    for(int i =0;i<n;i++)
        ans.push_back(i);
    return ans;
}