Minimum Comparisons in Invisible Sorting

In the virtual world, numbers are invisible. While escaping, a group of digits has escaped as well and now they are clamoring for help to be sorted. Xiao L only knows four sorting algorithms: selection sort, insertion sort, bubble sort, and merge sort.

In the worst-case scenario, Xiao L wonders what is the minimum number of comparisons needed to sort a sequence of n invisible numbers. Among the algorithms he knows, merge sort is the one that minimizes the number of comparisons in the worst-case. In a standard merge sort, when merging two sorted arrays of sizes a and b, the worst-case requires a+b-1 comparisons. This leads to the recurrence for the worst-case comparisons T(n):

$$T(n)=\begin{cases}0,&\text{if }n\le 1\\T(\lfloor n/2 \rfloor)+T(\lceil n/2 \rceil)+(n-1),&\text{if }n>1 \end{cases} $$

This recurrence can be shown to be equivalent to the formula:

$$T(n)= n\cdot \lceil \log_{2} n \rceil - 2^{\lceil \log_{2} n \rceil}+1 $$

Given a positive integer n, your task is to compute the minimum number of comparisons required in the worst-case to sort the sequence of invisible numbers using merge sort.

inputFormat

The input consists of a single line containing a positive integer n (1 ≤ n ≤ 10⁹), representing the number of invisible numbers.

outputFormat

Output a single integer which is the minimum number of comparisons required in the worst-case scenario to sort the sequence.

sample

1

0