Matryoşka
Matryoşkalar - bir-birinin içində yerləşdirilmiş, ölçüsü kiçildikcə açılan ənənəvi rus taxta kuklalarıdır. Matryoşkanı açıb içindən başqa bir matryoşka çıxarmaq olar, bu da öz növbəsində başqa birini ehtiva edə bilər və s.
Rus matryoşka muzeyində yaxınlarda eyni dizayna malik, lakin hər kolleksiyada fərqli sayda kukla olan matryoşka kolleksiyaları nümayiş etdirildi. Təəssüf ki, valideynlərinin nəzarətindən kənarda qalan çox maraqlı uşaqlar tapıldı və bütün matryoşkaları açıb sıraya düzdülər. Sırada n kukla yerləşdirilib, hər birinin tam ədədi ölçüsü var. Sizə matryoşka dəstlərini toplamaq lazımdır, nə dəstlərin sayını, nə də hər birindəki matryoşka sayını bilmədən. Yalnız məlumdur ki, hər dəst 1 ölçüsündən müəyyən m ölçüsünə qədər ardıcıl ölçülərə malik matryoşkalardan ibarətdir, bu ölçü dəstdən dəstə dəyişə bilər.
Toplama zamanı aşağıdakı qaydalara riayət etməlisiniz:
Siz yalnız daha böyük bir matryoşkanın içinə matryoşka və ya matryoşka qrupunu yerləşdirə bilərsiniz.
İki matryoşka qrupunu yalnız sırada yan-yana olduqda birləşdirə bilərsiniz.
Kukla bir qrupun üzvü olduqda, onu başqa bir qrupa köçürmək və ya qrupdan daimi ayırmaq mümkün deyil. Yalnız iki qrupun birləşdirilməsi zamanı müvəqqəti ayırmaq olar.
Vaxt puldur, ona görə də toplama mümkün qədər tez həyata keçirilməlidir. Bu məsələdə vaxt tələb edən yeganə əməliyyat matryoşkanın açılması və bağlanmasıdır, buna görə də onların sayını minimuma endirmək istəyirsiniz. Məsələn, [1, 2, 6] və [4] qruplarını birləşdirərkən açma əməliyyatlarının (və müvafiq olaraq bağlama əməliyyatlarının) ən az sayı ikidir, çünki yalnız 6 və 4 ölçülü matryoşkaları açmaq kifayətdir. [1, 2, 5] və [3, 4] qruplarını birləşdirərkən üç açma kifayətdir.
Bütün matryoşka dəstlərinin toplanması üçün kifayət qədər açma əməliyyatlarının ən az sayını tapacaq bir proqram yazın.
Giriş verilənləri
Giriş məlumatları bir testdən ibarətdir. Test iki sətirdən ibarətdir. Birinci sətir sırada ayrı-ayrı dayanan matryoşkaların sayını göstərən bir tam ədəd n (1 ≤ n ≤ 500) ehtiva edir. İkinci sətir sırada yerləşdirildikləri qaydada n təbii ədəd ehtiva edir - matryoşkaların ölçüləri. Matryoşkaların ölçüləri 1 ilə 500 arasında dəyişir.
Çıxış verilənləri
Matryoşka dəstlərinin toplanması üçün lazım olan açma əməliyyatlarının ən az sayını çıxarın. Əgər toplama mümkün deyilsə (uşaqlar çox maraqlı idilər və bəzi matryoşkaları özləri ilə apardılar), impossible sözünü çıxarın.