## 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:

,## 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:**

## Comments