Parçalanma
Feliks qarajda bir layihə üzərində işləyir. O, layihəsi üçün artıq təsirli bir ad tapıb: SuperFastZilla. Hal-hazırda SuperFastZilla-nın nə etməli olduğunu bilmir, lakin əmindir ki, bunu sürətli, çox sürətli etməlidir.
Bir gün o, SuperFastZilla-nın istifadə etdiyi sürətli alqoritmlərə baxmayaraq çox yavaş işlədiyini gördü. Feliks hesab edir ki, problem yaddaşın parçalanması ilə bağlı ola bilər.
SuperFastZilla-da yaddaş n blokdan ibarətdir. SuperFastZilla yaddaş üzərində bəzi əməliyyatlar həyata keçirir. Hər bir blok yalnız bir əməliyyatdan istifadə edir, i-ci blok a[i]-ci əməliyyatda istifadə olunur.
Feliks bu blokları istifadə olunan əməliyyatın indeksinə görə sıralamaq istəyir. Bunu daha sürətli etmək üçün Feliks yaddaşı ardıcıl blokların minimal sayına bölmək və sonra bu seqmentləri elə yenidən düzəltmək istəyir ki, blokların sıralanmış massivini əldə etsin. Yenidən qruplaşdırmadan sonra bloklardakı əməliyyat indekslərinin sırası artmayan olmalıdır.
Feliksə yaddaşı elə bölməyə kömək edin ki, seqmentlərin sayı minimum olsun.
Məsələn, əgər a = [2, 3, 1, 1, 2, 2, 1] olarsa, onu üç hissəyə bölmək olar: [2, 3], [1, 1, 2, 2] və [1]. Bu hissələri yenidən düzəltməklə sıralanmış massiv əldə etmək olar: [1], [1, 1, 2, 2], [2, 3].
Giriş məlumatları
Birinci sətir n ədədini (1 ≤ n ≤ 10^5) ehtiva edir. Növbəti sətir n ədəd a[i] (1 ≤ a[i] ≤ 10^5) ehtiva edir.
Çıxış məlumatları
Birinci sətir m tam ədədini - seqmentlərin minimal sayını ehtiva edir. Növbəti sətir m ədədini - soldan sağa doğru seqmentlərin uzunluqlarını ehtiva edir.