Matryoşka Kuklaları
Adam, Matryona'dan bir qutu dolu Matrёşka kuklaları (Rus ənənəvi kuklaları) aldı. Qutunu açdığında, içindən bir çox kukla və bir qeyd çıxdı:
Salam Adam, ümid edirəm ki, bu kuklaları bəyənəcəksən. Amma üzr istəyirəm, onları düzəltməyə vaxtım olmadı. Görəcəksən ki, hər kuklanın alt tərəfində kiçik bir kuklanı içərisinə yerləşdirməyə imkan verən boş bir deşik var.
...
Sənin,
Matryona
Adam, vitrində artıq çox əşyası olduğu üçün, kuklaları yığaraq ən xarici kuklaların sayını azaltmağa qərar verir. Matryona'nın göndərdiyi kuklalar eyni formadadır, lakin müxtəlif ölçülərdədir. Yəni, kukla i tək bir rəqəmlə h_i hündürlüyünü ifadə edir. Kukla i yalnız h_i < h_j olduqda başqa bir kuklanın j içərisinə yerləşə bilər. Həmçinin, kuklalar elə dizayn edilib ki, hər kukla içərisində ən çox bir kukla ola bilər. Adam Matrёşka kuklalarının nəhəng kolleksiyasını yığarkən, onun vitrində nə qədər yerə ehtiyacı olduğunu müəyyən etmək üçün ən xarici kuklaların minimum sayını hesablaya bilən bir proqram yaza bilərsinizmi?
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Hər test halı bir tam ədəd N, 1 ≤ N ≤ 10^5, Matrёşka kuklalarının sayını göstərən bir sətirlə başlayır. Bunun ardınca N sətir gəlir, hər biri i-ci kuklanın hündürlüyünü sm ilə göstərən bir tam ədəd h_i, 1 ≤ h_i ≤ 10^9. Giriş N = 0 olan bir sətirlə bitir, bu işlənməməlidir.
Çıxış verilənləri
Hər test halı üçün, verilmiş kuklaların optimal şəkildə yığılması nəticəsində əldə edilə bilən ən xarici kuklaların minimum sayını göstərən bir tam ədəd çap edin.