Не по порядку (Платина)

Дбаючи про довгострокові кар'єрні перспективи за межами ферми, корова Бессі почала вивчати алгоритми на різних онлайн-сайтах з програмування. Її два улюблені алгоритми — це "бульбашкове сортування" та "швидке сортування", але, на жаль, Бессі легко їх плутає і в підсумку реалізує досить дивний гібрид цих двох алгоритмів!

Назвемо позицію між елементами $i$ та i + 1 масиву $A$ точкою поділу, якщо максимум серед A_0, \ldots, A_i не більший за мінімум серед A_{i+1}, \ldots, A_{n-1}. Бессі пам'ятає, що швидке сортування перевпорядковує масив так, щоб у ньому з'явилася точка поділу, а потім рекурсивно сортує обидві частини A_0, \ldots, A_i та A_{i+1}, \ldots, A_{n-1}. Однак, хоча вона правильно зазначає, що всі точки поділу масиву можна знайти за лінійний час, вона забула, як саме швидке сортування має перевпорядковувати масив, щоб швидко створити точку поділу! У тому, що може виявитися найгіршою алгоритмічною помилкою в історії сортування, вона приймає невдале рішення використати для цього бульбашкове сортування.

Ось опис реалізації Бессі для сортування масиву $A$. Спочатку вона пише просту функцію, яка виконує один прохід бульбашкового сортування:

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

Рекурсивний код її функції швидк(увато)го сортування структурований наступним чином:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A)
   divide A at all partition points; recursively quickish_sort each piece
}

Бессі цікаво, наскільки швидко працюватиме її код. Для простоти вона вважає, що кожна ітерація основного циклу займає лінійний час, тому вона збільшує глобальну змінну work\_counter всередині циклу відповідно, щоб відстежувати загальний обсяг роботи, виконаної алгоритмом.

За заданим вхідним масивом передбачте остаточне значення work\_counter після того, як масив буде відсортовано функцією quickish\_sort.