## Editorial for An Animal Contest 6 P2 - G-Pop

Remember to use this editorial 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.

Authors: andrewtam, julian33

Solution for 20%

Note that if , then we need exactly distinct bands.

Solution for 50%

An example of an ordering that is valid is .

Solution for 100%

Let be the plan that we output. For the remaining , we must maximize the number of indices where . Let's call good if we can do this. First, let's define as the minimal such that . If there is no such that , then . Observe that is good if and only if . This is because if there exists some such that . So, if we make , then there will be identical bands playing within some . On the other hand, if , there clearly exists no where and are in . Initially, set . Then, for each , if . Otherwise, , making sure that if we set it to .

Time Complexity: