排序（sort）

题目描述

Kaguya 是一个喜欢秩序的女孩子。她常常收到很多序列作为礼物，有时她希望对某些序列进行排序。

今天，Ayu 又送了 Kaguya 一个排列 a[1...n]。Kaguya 希望按照如下代码对其进行排序：

function sort(a[1...len(a)]):
    if len(a) <= 1 then return a
    let pivot = a[ceil(len(a) / 2)]
    let al, ag = empty sequence
    for i in 1...len(a) do
        let cmpcnt = cmpcnt + 1
        if a[i] < pivot then append a[i] to al
        if a[i] > pivot then append a[i] to ag
    return sort(al) + [pivot] + sort(ag)

Kaguya 比较关心排序需要的比较次数，所以希望你求出：用该函数对 a[1...n] 进行一次排序后，cmpcnt 会增加多少。

输入格式

输入的第一行包含一个整数 n，表示要排序的排列长度。

输入的第二行包含 n 个整数 a[1...n]，表示要排序的排列。

输出格式

输出一行包含一个整数，表示一次排序后 cmpcnt 的变化量。

样例 1 输入

5
4 3 5 1 2

样例 1 输出

11

样例 1 解释

作为函数参数的非空序列共有以下五个：

• [4, 3, 5, 1, 2]
• [4, 3, 1, 2]
• [4]
• [1, 2]
• [2]

子任务

对于所有测试数据保证：

• 1 <= n <= 7 * 10^5
• 1 <= a[i] <= n
• 对任意 i != j，都有 a[i] != a[j]

每个测试点的具体限制如下：