Qaydadan Çıxıb (Platin)

Fermadan kənarda uzunmüddətli karyera imkanlarını nəzərə alaraq, inək Bessie müxtəlif onlayn proqramlaşdırma saytlarında alqoritmlər öyrənməyə başlayıb. Onun ən sevdiyi iki alqoritm "bubble sort" (köpük sıralaması) və "quicksort" (sürətli sıralama)dır, lakin təəssüf ki, Bessie bunları asanlıqla qarışdırır və nəticədə ikisinin olduqca qəribə hibridini tətbiq edir!

$A$ massivinin $i$ və i + 1 elementləri arasındakı mövqeyə, əgər A_0, \ldots, A_i-nin maksimumu A_{i+1}, \ldots, A_{n-1}-in minimumundan böyük deyilsə, bölgü nöqtəsi deyək. Bessie xatırlayır ki, quicksort massivi elə yenidən tərtib edir ki, orada bölgü nöqtəsi yaransın, sonra isə iki hissəni — A_0, \ldots, A_i və A_{i+1}, \ldots, A_{n-1} — rekursiv olaraq sıralayır. Lakin, baxmayaraq ki, o düzgün olaraq qeyd edir ki, massivin bütün bölgü nöqtələri xətti zamanda tapıla bilər, o, quicksort-un massivi necə yenidən düzəcəyini — bölgü nöqtəsini tez yaratmaq üçün — unudub! Sıralama tarixindəki ən böyük alqoritmik səhv ola biləcək bir addımla, o, bu tapşırıq üçün bubble sort istifadə etmək kimi bədbəxt qərar qəbul edir.

Bessie-nin $A$ massivini sıralamaq üçün implementasiyasının qısa icmalı budur. Əvvəlcə, o, bubble sort-un bir keçidini yerinə yetirən sadə funksiya yazır:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Onun rekursiv quick(ish) sort funksiyasının kodu belə qurulub:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Əsas dövrə
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (A-da bölgü nöqtəsi yoxdur)
   A-nı bütün bölgü nöqtələrində böl; hər bir hissəni rekursiv olaraq quickish_sort ilə sırala
}

Bessie onun kodunun nə qədər sürətli işləyəcəyini öyrənmək istəyir. Sadəlik üçün o, güman edir ki, əsas dövrün hər bir iterasiyası xətti zamanda baş verir, buna görə də dövrün içində qlobal work\_counter dəyişənini uyğun olaraq artırır ki, alqoritmin yerinə yetirdiyi ümumi işi izləsin.

Verilmiş giriş massivi üçün, massiv quickish\_sort tərəfindən sıralandıqdan sonra work\_counter-in son dəyərini təxmin edin.