Enchanted Music Boxes#4223
Lyra, a traveling bard, just received a large crate filled with enchanted music boxes from Master Melodius, a renowned magical craftsman. When she opened the crate, dozens of beautifully ornate boxes tumbled out along with a letter:
Dear Lyra,
I hope these enchanted music boxes bring joy to your performances. My apologies for the disarray—I ran out of time to organize them properly before your departure. Each box is imbued with dimensional magic: you'll notice that smaller boxes can be placed inside larger ones, where they nestle perfectly and continue to play their melodies in harmony.
May your songs enchant the realm,
Master Melodius
Lyra's traveling wagon already overflows with musical instruments and magical artifacts. To save precious space, she decides to nest the music boxes optimally, minimizing the number of outermost boxes she needs to store.
Each enchanted music box has a unique size, represented by a single number s_i denoting its dimensions. A music box can fit inside another box if and only if s_i < s_j. Due to the nature of the dimensional enchantments, each box can contain at most one other box directly inside it (though that inner box might itself contain another box, creating a nested chain).
As Lyra organizes her collection of enchanted music boxes, can you help her determine the minimum number of outermost boxes needed for her wagon?
The input consists of multiple test cases. Each test case begins with a line containing an integer (1 \leq N \leq 10^5), denoting the number of enchanted music boxes. This is followed by lines, each with a single integer s_i (1 \leq s_i \leq 10^9), denoting the size of the -th music box. Input is followed by a single line with N = 0, which should not be processed.
For each test case, print a single line containing an integer representing the minimum number of outermost boxes that can be obtained by optimally nesting the given enchanted music boxes.
Example 1