Yeni başlayan biri üçün ustaya tapşırıq
Çeşidləmənin sadə olduğunu düşünürsünüz? Vaxtınız olmadıqda bu, heç də belə deyil.
Həyatımızda gözlənilməz qəribə hadisələr tez-tez baş verir. Məsələn, artan sıraya görə çeşidlənməli olan A massiviniz var. Problem ondadır ki, həqiqətən də buna vaxtınız yoxdur.
Xoşbəxtlikdən, dostunuz massivlərin çeşidlənməsində çox bacarıqlıdır, buna görə də ondan kömək istəməyə qərar verdiniz. Siz düşünürsünüz ki, dostunuzun xüsusi bacarıqları onun konseptual yanaşması ilə bağlıdır. O, bir saniyədə massivdən bir elementi çıxarıb ya əvvələ, ya da sonuna yerləşdirə bilir.
Məsələn, massiv 4 2 5 6 1 3 şəklindədir. 5-i çıxarıb əvvələ qoyduqda, 5 4 2 6 1 3 alırıq. Əgər 2-ni çıxarıb sona qoysaq, 4 5 6 1 3 2 alırıq.
Əlbəttə ki, dostunuz bütün əməliyyatları kifayət qədər sürətli yerinə yetirir, çünki vaxtını itirmək istəmir. Siz yalnız bilmək istəyirsiniz ki, massiv çeşidləndikdən sonra digər faydalı işlər üçün nə qədər vaxtınız qalacaq.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 3∙10^5) elementlərinin sayını A-da ehtiva edir. İkinci sətir n ədəd tam ədədlər A[i] (1 ≤ A[i] ≤ 10^6) ehtiva edir.
Çıxış məlumatları
Dostunuzun A massivini çeşidləməsi üçün lazım olan ən kiçik vaxtı saniyələrlə çıxarın.