题目背景

小L从虚拟世界里出来啦！

加强版链接

题目描述

逃出来的同时，也有一部分数码逃了出来，吵着闹着让小L帮他们排序

虚拟世界的数码都是不可见的

小L目前只会选择排序，插入排序，冒泡排序，归并排序

所以小L想问他在最坏情况下最少需要几次比较，才能使序列有序

排序的模板代码

输入格式

输入仅有一行，给定一个正整数 $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}$

数据保证随机