Ваня принес на кухню рулет, который он хочет разделить с коллегами. Для этого он хочет разрезать рулет на
N
равных частей. Разумеется, рулет можно резать только поперек. Соответственно, Костя сделает
N
−
1
разрез ножом через равные промежутки.
По возвращению с кофе-брейка Ваня задумался — а можно ли было обойтись меньшим числом движений, будь нож Вани бесконечно длинным (иначе говоря, если он мог бы сделать сколько угодно разрезов за раз, если эти разрезы лежат на одной прямой)? Считается, что места для разрезов намечены заранее, и все разрезы делаются с ювелирной точностью.
Оказывается, что можно. Например, если Ваня хотел бы разделить рулет на 4 части, он мог бы обойтись двумя разрезами — сначала он разделил бы рулет на две половинки, а потом совместил бы две половинки и разрезал обе пополам одновременно.
Вам дано число
N
, требуется сказать, каким минимальным числом разрезов можно обойтись.