题目描述

留意着农场之外的长期职业生涯的可能性，奶牛 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 的最终值。

7
20
2
3
4
9
8
7

12

提示

在这个例子中，数组初始为 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