Out of Sorts

Bessie the cow is thinking about a career beyond the farm, so she has started learning algorithms from online coding sites. Her two favorite algorithms are bubble sort and quicksort. She keeps confusing the two, and what she ends up implementing is an odd hybrid of both.

Call the gap between positions $i$ and $i+1$ of an array A a partition point when the maximum of A[0..i] is no larger than the minimum of A[i+1..N-1]. Quicksort rearranges an array so that it has a partition point and then sorts the two sides A[0..i] and A[i+1..N-1] recursively. Bessie remembers that much, and she also knows, correctly, that every partition point of an array can be found in linear time. What she has forgotten is how quicksort rearranges the array to create a partition point quickly, so she uses one pass of bubble sort for that job.

One pass of bubble sort is written like this:

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

Her recursive sort is then structured like this:

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 wants to know how fast her code runs. She treats one iteration of the main loop as work proportional to the length of the array it runs on, so she adds that length to the global variable work_counter inside the loop. Given the initial array, predict the final value of work_counter after quickish_sort runs on it.

The first line contains $N$ ($1 \le N \le 100000$). Each of the next $N$ lines contains one element of the array, A[0] through A[N-1], and every element is an integer between $0$ and $10^9$. The elements are not guaranteed to be distinct.

Print the final value of work_counter.

Start with the array 20 2 3 4 9 8 7. One pass of bubble sort adds 7 to the counter and leaves 2 | 3 | 4 | 9 8 7 | 20, where | marks a partition point. The pieces 2, 3, 4 and 20 have length 1, so they cost nothing. The piece 9 8 7 takes one iteration of the main loop (3 units of work) and becomes 8 7 | 9, and one last iteration over 8 7 (2 units of work) finishes the sort. The counter ends at 12.