P5626 [AFOI-19] Digital Sorting

Little L has come out of the virtual world! --- **Enhanced version [link](https://www.luogu.org/problem/P5634)**

While escaping, some “digits” also escaped. They kept making noise and asked Little L to help sort them. The digits in the virtual world are invisible. Little L currently only knows selection sort, insertion sort, bubble sort, and merge sort. So Little L wants to ask: in the worst case, what is the minimum number of comparisons needed to make the sequence sorted? ------- [Template code for sorting](https://www.luogu.org/paste/fdtepscp)

There is only one line of input: a positive integer $n$, representing the length of the sequence.

Output the minimum number of comparisons.

- **Sample $1$ Explanation** For a sequence of length $4$, merge sort splits it into $2$ groups, with $2$ elements in each group. The $2$ elements in each group are compared once. During merging, the worst case needs $3$ comparisons, so the total is $3+1+1=5$. - **Constraints** For $10\%$ of the testdata, $n \leq 1000$. For $30\%$ of the testdata, $n \leq 1000000$. For $100\%$ of the testdata, $n \leq 10^{16}$. **The testdata is guaranteed to be random.** Translated by ChatGPT 5