Description

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

Input Format

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

Output Format

Output the minimum number of comparisons.

4

5

5

8

Hint

• 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