Out of Sorts (Platinum)

Keeping an eye on long-term career opportunities beyond the farm, Bessie the cow has started learning algorithms on various online coding websites. Her two favorite algorithms are "bubble sort" and "quicksort", but unfortunately, Bessie easily confuses them and ends up implementing a rather odd hybrid of the two!

Let us call the position between elements $i$ and i + 1 of an array $A$ a partition point if the maximum of A_0, \ldots, A_i is not larger than the minimum of A_{i+1}, \ldots, A_{n-1}. Bessie remembers that quicksort rearranges an array so that it has a partition point and then recursively sorts the two parts A_0, \ldots, A_i and A_{i+1}, \ldots, A_{n-1}. However, although she correctly notes that all partition points of an array can be found in linear time, she has forgotten how quicksort is supposed to rearrange the array to quickly create a partition point! In what may prove to be the worst algorithmic blunder in the history of sorting, she makes the unfortunate decision to use bubble sort for this task.

Here is an outline of Bessie's implementation for sorting an array $A$. First, she writes a simple function that performs one pass of 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]
}

The recursive code of her quick(ish) sort function is structured as follows:

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 is curious how fast her code will run. For simplicity, she assumes that each iteration of the main loop takes linear time, so she increases the global variable work\_counter inside the loop accordingly to keep track of the total work done by the algorithm.

Given the input array, predict the final value of work\_counter after the array is sorted by quickish\_sort.