Problem Background

Xiao L has come out from the virtual world!

Enhanced Version Link

Problem Description

While escaping, some digital entities also escaped and are clamoring for Xiao L to sort them.

The digital entities in the virtual world are invisible.

Xiao L currently knows only selection sort, insertion sort, bubble sort, and merge sort.

Therefore, Xiao L wants to know the minimum number of comparisons he needs in the worst case to make the sequence sorted.

Sorting Template Code

Input Format

The input consists of a single line, providing a positive integer $n$, representing the length of the sequence.

Output Format

Output the minimum number of comparisons.

Sample Input and Output

Sample Input #1

4

Sample Output #1

5

Sample Input #2

5

Sample Output #2

8

Notes

• Sample 1 Explanation

For a sequence of length 4, using merge sort, it is divided into 2 groups, each with 2 elements. Each group compares once, and the worst-case comparison during merging is 3 times, so it is $3 + 1 + 1 = 5$.

• Data Range

For 10% of the data, $n \leq 1000$

For 30% of the data, $n \leq 1000000$

For 100% of the data, $n \leq 10^{16}$

Data is guaranteed to be random

见题面 Input 部分

见题面 Output 部分