P4372 [USACO18OPEN] Out of Sorts P

Eyeing the possibility of a long-term career beyond the farm, the cow Bessie starts learning algorithms on various online programming sites. Her two favorite algorithms are "bubble sort" and "quicksort," but unfortunately, Bessie easily mixes them up and ends up implementing a strange hybrid algorithm! If in array $A$ the maximum of $A[0 \ldots i]$ is no greater than the minimum of $A[i+1 \ldots N-1]$, then the position between elements $i$ and $i+1$ is called a "partition point." Bessie also remembers that quicksort involves rearranging the array to produce a partition point, and then recursively sorting $A[0 \ldots i]$ and $A[i+1 \ldots N-1]$ on the two sides. However, although she correctly notes that all the partition points in the array can be found in linear time, she forgets how quicksort should rearrange the array to quickly construct a partition point. In what is perhaps the worst blunder in the history of sorting algorithms, she makes the unfortunate decision to use bubble sort to perform this task. Below is a summary of Bessie's initial implementation for sorting array $A$. She first 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 quickish sort function is 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 can run. For simplicity, she decides that each iteration of the main loop takes linear time, so she tracks the total amount of work done by the entire algorithm by increasing a global variable, work_counter. Given an input array, please predict the final value of work_counter after the quickish_sort function processes this array.

The first line of input contains $N$ ($1 \leq N \leq 100{,}000$). The next $N$ lines describe $A[0] \ldots A[N-1]$, each being an integer in the range $0 \ldots 10^9$. The input numbers are not guaranteed to be distinct.

Output the final value of work_counter.

In this example, the array initially is `20 2 3 4 9 8 7`. After one pass of bubble sort (adding $7$ units of work), we obtain `2 | 3 | 4 | 9 8 7 | 20`, where `|` denotes a partition point. The problem then splits into recursive subproblems, including sorting `2`, `3`, `4`, and `20` (each costing $0$ units of work) and sorting `9 8 7`. For the subproblem `9 8 7`, one iteration of the main loop ($3$ units of work) yields `8 7 | 9`, after which the final pass on `8 7` ($2$ units of work) effectively completes the sort. Source: Brian Dean. Translated by ChatGPT 5