Украинские олимпиаы: Украинская олимпиада 2007

Рассмотрим цепочку, состоящую из N колец. Какое минимальное количество колец необходимо расцепить, чтобы из оставшихся кусков можно было собрать цепочки любой длины от 1 до N колец? При создании новых цепочек можно использовать расцепленные кольца.

Например, при N=21, достаточно расцепить всего 2 кольца таким образом, чтобы получились куски длинной 3, 5 и 11. Два расцепленных кольца считаются кусками единичной длины.

Напишите программу, которая по натуральному числу N – длине исходной цепочки, находит минимальное количество колец, которые необходимо расцепить для достижения описанной цели.

Формат входных данных

Единственная строка входного файла содержит одно целое число N (1≤N≤10⁹).

Формат выходных данных

Единственная строка выходного файла должна содержать одно целое число – найденное минимальное количество колец.

24

3