Compute prefix sums of count of nodes in each level
for ( ll i = 1 ; i < len ; ++ i ) { prefix [ i ] = arr [ i ] + prefix [ i - 1 ] ; } vector < ll > :: iterator it = lower_bound ( prefix . begin ( ) , prefix . end ( ) , N ) ;