#include "partition.h"
#include <bits/stdc++.h>
std::vector<int> solve(std::vector<int> V)
{
    long long sum = 0 ;
    int ind = 0 ;
    std :: vector < std :: pair < int , int > > A ;
    for ( auto it : V )
    {
        sum += it ;
        A.push_back( {it,ind} ) ;
        ind ++ ;
    }
    sum /= 2 ;
    sort ( A.begin() , A.end() ) ;
    int n = A.size() ;
    n -- ;
    int l = n / 2 + 1 , r = n / 2 + 1 ;
    long long s = 0 ;
    while ( r <= n && s < sum )
    {
        s += A[r].first ;
        r ++ ;
    }
    r -- ;
    if ( ( r - l + 1 ) != ( n + 1 ) / 2 )
    {
        s -= A[r].first ;
        while ( l >= 0 && s < sum && ( r - l + 1 ) < ( n + 1 ) / 2 )
        {
            l -- ;
            if ( l >= 0 )
                s += A[l].first ;
        }
        if ( l >= 0 )
            s -= A[l].first ;
        l ++ ;
        s += A[r].first ;
    }
    std :: vector < int > ans ;
    if ( s >= sum )
    {
        for ( int i = l ; i <= r ; i ++ )
            ans.push_back(A[i].second) ;
        for ( int i = 0 ; i < l ; i ++ )
            ans.push_back(A[i].second) ;
        for ( int j = r + 1 ; j <= n ; j ++ )
            ans.push_back(A[j].second) ;
    }
    else
    {
        for ( int i = 0 ; i < l ; i ++ )
            ans.push_back(A[i].second) ;
        for ( int j = r + 1 ; j <= n ; j ++ )
            ans.push_back(A[j].second) ;
        for ( int i = l ; i <= r ; i ++ )
            ans.push_back(A[i].second) ;
    }
    return ans ;
}