#include "partition.h"

std::vector<int> solve(std::vector<int> A)
{
    long long sum = 0 ;
    for ( auto it : A )
        sum += it ;
    sum /= 2 ;
    sort ( A.begin() , A.end() ) ;
    int n = A.size() ;
    n -- ;
    int l = n / 2 + 1 , r = n / 2 + 1 ;
    long long sum = 0 ;
    while ( r <= n && s < sum )
    {
        s += A[r] ;
        r ++ ;
    }
    r -- ;
    if ( ( r - l + 1 ) != ( n + 1 ) / 2 )
    {
        s -= A[r] ;
        while ( l >= 0 && s < sum && ( r - l + 1 ) < ( n + 1 ) / 2 )
        {
            l -- ;
            if ( l >= 0 )
                s += A[l] ;
        }
        if ( l >= 0 )
            s -= A[l] ;
        l ++ ;
        s += A[r] ;
    }
    vector < int > ans ;
    if ( s >= sum )
    {
        for ( int i = st ; i <= dr ; i ++ )
            ans.push_back(i) ;
        for ( int i = 0 ; i < st ; i ++ )
            ans.push_back(i) ;
        for ( int j = dr + 1 ; j <= n ; j ++ )
            ans.push_back(j) ;
    }
    else
    {
        for ( int i = 0 ; i < st ; i ++ )
            ans.push_back(i) ;
        for ( int j = dr + 1 ; j <= n ; j ++ )
            ans.push_back(j) ;
        for ( int i = st ; i <= dr ; i ++ )
            ans.push_back(i) ;
    }
    return ans ;
}
