Продолжаем банкет! Хайди уже знает, сколько минимум мозгов должно быть в сундуке, чтобы она смогла забрать хотя бы один. Однако же отправиться одной в гущу диких и голодных зомби было достаточно рискованным приключением. Теперь Хайди интересно: чему равняется минимально возможное количество мозгов в сундуке, при котором она смогла бы выбраться с вечеринки живой (возможно с пустыми руками)?
Правила вечеринки по поеданию мозгов остаются такими же как в предыдущей подзадаче: присутствуют n - 1 зомби и Хайди, мозги распределяются по такой же схеме, при которой предложение должны принять как минимум половина присутствующих, чтобы Хайди осталась в живых.
Выходные данные
Выведите одно целое число: минимальное количество мозгов в сундуке, при котором у Хайди есть надежда выжить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
0
|
|
2
|
3
|
1
|
|
3
|
99
|
49
|