Minimal Comparisons in Worst-Case Sorting

In the virtual world the numbers are invisible, and Little L can only perform a few types of sorting: selection sort, insertion sort, bubble sort, and merge sort. He now wonders: In the worst-case scenario, what is the minimum number of comparisons required to sort a sequence of n numbers?

The theoretical lower bound for any comparison-based sorting algorithm is given by the formula:

[ \lceil \log_2(n!) \rceil ]

Note that if n \leq 1, no comparisons are needed.

inputFormat

The input consists of a single integer \(n\) representing the number of elements.

outputFormat

Output a single integer representing the minimum number of comparisons required in the worst-case to sort the array. This number is \(\lceil \log_2(n!) \rceil\).

sample

1

0