## Editorial for COCI '16 Contest 6 #3 Turnir

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

First, we need to notice that the only relevant information for each number is the number of numbers larger than it. This is relevant because only the larger numbers will continue to the next level, and all the other numbers will accompany the current number to the top. This information is easily obtained by sorting the numbers.

Let's try to calculate the highest level can reach. For the zeroth level, there obviously cannot be a single larger number than , i.e., the number of numbers larger than it must be . In order to reach the first level, there must be at most numbers larger than it, because otherwise, at least one number larger than will 'fight' with it, which will result in not passing to the next level. In the case when there are more than numbers larger than , should be at a level below the first one. Now, in order for to be at the second level, the number of numbers larger than it must not exceed . Why?

It is easy to see that numbers can be left on the level above at the other side of the tree, then we are left with numbers with in there. On the current second level, we make the same decision where we see whether we can leave all larger numbers in the second subtree sized , in order for to freely rise to the top of its subtree, to level . We follow this algorithm, subtracting the descending powers of from the number of numbers larger than .

The total complexity of the algorithm is .

## Comments