A2642 | Out of Sorts P

留意着农场之外的长期职业生涯的可能性，奶牛Bessie开始在不同的在线编程网站上学习算法。她最喜欢的两个算法是“冒泡排序”和“快速排序”，但是不幸的是Bessie轻易地把它们搞混了，最后实现了一个奇怪的混合算法！
如果数组$A$中$A[...i]$的最大值不大于$A[i+1 \ldots]$的最小值，我们就称元素$i$和$i+1$之间的位置为一个“分隔点”。Bessie还记得快速排序包含对数组的重排，产生了一个分隔点，然后要递归对两侧的$A[...i]$和$A[i+1 \ldots]$排序。然而，尽管她正确地记下了数组中所有的分隔点都可以在线性时间内被求出，她却忘记快速排序应该怎么重排来快速构造一个分隔点了！在这个可能会被证明是排序算法的历史中最糟糕的算法性失误之下，她做出了一个不幸的决定，使用冒泡排序来完成这个任务。

以下是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的最终值。