Out of Sorts (Platinum)

Tenendo d'occhio le opportunità di carriera a lungo termine al di fuori della fattoria, la mucca Bessie ha iniziato a imparare algoritmi su vari siti web di programmazione online. I suoi due algoritmi preferiti sono il "bubble sort" e il "quicksort", ma sfortunatamente, Bessie li confonde facilmente e finisce per implementare un ibrido piuttosto strano dei due!

Chiamiamo la posizione tra gli elementi $i$ e i + 1 di un array $A$ un punto di partizione se il massimo di A_0, \ldots, A_i non è maggiore del minimo di A_{i+1}, \ldots, A_{n-1}. Bessie ricorda che il quicksort riorganizza un array in modo che abbia un punto di partizione e poi ordina ricorsivamente le due parti A_0, \ldots, A_i e A_{i+1}, \ldots, A_{n-1}. Tuttavia, sebbene noti correttamente che tutti i punti di partizione di un array possono essere trovati in tempo lineare, ha dimenticato come il quicksort dovrebbe riorganizzare l'array per creare rapidamente un punto di partizione! In quella che potrebbe rivelarsi la peggiore svista algoritmica nella storia dell'ordinamento, prende la sfortunata decisione di usare il bubble sort per questo compito.

Ecco uno schema dell'implementazione di Bessie per ordinare un array $A$. Prima, scrive una semplice funzione che esegue un passaggio di bubble sort:

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

Il codice ricorsivo della sua funzione quick(ish) sort è strutturato come segue:

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
}

Bessie è curiosa di sapere quanto velocemente girerà il suo codice. Per semplicità, assume che ogni iterazione del ciclo principale richieda tempo lineare, quindi incrementa la variabile globale work\_counter all'interno del ciclo di conseguenza per tenere traccia del lavoro totale svolto dall'algoritmo.

Dato l'array di input, predici il valore finale di work\_counter dopo che l'array è stato ordinato da quickish\_sort.