P4372 [USACO18OPEN] Out of Sorts P

留意着农场之外的长期职业生涯的可能性，奶牛 Bessie 开始在不同的在线编程网站上学习算法。她最喜欢的两个算法是“冒泡排序”和“快速排序”，但不幸的是，Bessie 轻易地把它们搞混了，最后实现了一个奇怪的混合算法！ 如果数组 $A$ 中 $A[0 \ldots i]$ 的最大值不大于 $A[i+1 \ldots N-1]$ 的最小值，我们就称元素 $i$ 和 $i+1$ 之间的位置为一个“分隔点”。Bessie 还记得快速排序包含对数组的重排，产生一个分隔点，然后递归对两侧的 $A[0 \ldots i]$ 和 $A[i+1 \ldots N-1]$ 排序。然而，尽管她正确地记下了数组中所有的分隔点都可以在线性时间内求出，她却忘记了快速排序应该如何重排来快速构造一个分隔点！在这个可能是排序算法历史上最糟糕的失误之下，她做出了一个不幸的决定：使用冒泡排序来完成这个任务。 以下是 Bessie 最初对数组 $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 } ``` Bessie 好奇于她的代码能够运行得多快。简单起见，她计算出主循环的每一轮都消耗线性时间，因此她通过增加一个全局变量 `work_counter` 的值来跟踪整个算法完成的总工作量。 给定一个输入数组，请预测 `quickish_sort` 函数接收这个数组后，变量 `work_counter` 的最终值。

输入的第一行包含 $N$（$1 \leq N \leq 100,000$）。接下来的 $N$ 行描述了 $A[0] \ldots A[N-1]$，每个数都是一个范围在 $0 \ldots 10^9$ 的整数。输入数据不保证各不相同。

输出 `work_counter` 的最终值。

在这个例子中，数组初始为 `20 2 3 4 9 8 7`。在一轮冒泡排序之后（增加 $7$ 的工作量），我们得到 `2 | 3 | 4 | 9 8 7 | 20`，其中 `|` 表示一个分隔点。于是问题被分成了递归的子问题，包括对 `2`、`3`、`4`、`20` 排序（每个消耗 $0$ 单元的工作量）和对 `9 8 7` 排序。对于 `9 8 7` 这个子问题，主循环的一轮（$3$ 单元工作量）得到 `8 7 | 9`，在此之后最后一轮处理 `8 7`（$2$ 单元工作量）就有效地完成了排序。 题目来源：Brian Dean