# CFR 806 C. Prairie Partition ( Binary Search, Greedy )

Problem - C - Codeforces

The first line contains a single integer n (1 ≤ n ≤ 1e5) — the number of numbers given from Alice to Borys.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1e12; a1 ≤ a2 ≤ ... ≤ an) — the numbers given from Alice to Borys.

O( N lg N ) / O( N )

```from functools import reduce

N = int( input() )
A = list( map( int, input().split() ) )

cntp2 = [ 0 for i in range( 50 ) ]
zanp2 = [ 0 for i in range( 50 ) ]

for i in range( N ):
t = max( list( filter( lambda x: A[ i ] >> x & 1, range( 50 ) ) ) )
if 1 << t == A[ i ]:
cntp2[ t ] += 1
else:
zanp2[ t ] += 1

def ok( gol_len ):
c = [ v for v in cntp2 ]
z = [ v for v in zanp2 ]
for i in range( 50 ):
if c[ i ] <= gol_len:
gol_len = c[ i ]
else:
z[ i ] += c[ i ] - gol_len
c[ i ] = gol_len
sc = reduce( list.__add__, ( list( j for i in range( c[ j ] - c[ j + 1 ] ) ) for j in range( 50 - 1 ) ) )
sz = reduce( list.__add__, ( list( j for i in range( z[ j ] ) ) for j in range( 50 - 1 ) ) )
return len( sc ) >= len( sz ) and all( sc[ i + len( sc ) - len( sz ) ] >= sz[ i ] for i in range( len( sz ) ) )

if not ok( cntp2[ 0 ] ):
exit( print( -1 ) )

lb, ub = 0, cntp2[ 0 ] # ( lb, ub ]
while lb + 1 < ub:
mid = lb + ub >> 1
if ok( mid ):
ub = mid
else:
lb = mid
print( ' '.join( str( i ) for i in range( ub, cntp2[ 0 ] + 1 ) ) )
```