【AFOI-19】数码排序

小L从虚拟世界里出来啦！ --- **加强版[链接](https://www.luogu.org/problem/P5634)**

逃出来的同时，也有一部分数码逃了出来，吵着闹着让小L帮他们排序 虚拟世界的数码都是不可见的 小L目前只会选择排序，插入排序，冒泡排序，归并排序 所以小L想问他在最坏情况下最少需要几次比较，才能使序列有序 ------- [排序的模板代码](https://www.luogu.org/paste/fdtepscp)

输入仅有一行，给定一个正整数 $n$，表示序列的长度

输出最小的比较次数

4

5

5

8

- **样例$1$解释** 长度为$4$的序列归并调用，分成$2$组，一组$2$个元素。$2$个元素分别比较一次， 合并时最坏比较$3$次，所以是$3+1+1=5$。 - **数据范围** 对于$10\%$的数据，$n \leq 1000$ 对于$30\%$的数据，$n \leq 1000000$ 对于$100\%$的数据，$n \leq 10^{16}$ **数据保证随机**