У вас есть \(n\) монет, каждая из них имеет номинал \(1\).
Распределите их на пакеты таким образом, что любая сумма \(x\) (\(1 \leq x \leq n\)) может быть набрана с использованием некоторого (возможно одного или всех) количества этих пакетов.
Каждый пакет можно использовать только целиком или не использовать вовсе. Ни один пакет нельзя использовать больше одного раза, чтобы набрать одну сумму \(x\), однако тот же самый пакет можно переиспользовать, чтобы набрать другие суммы \(x\).
Найдите минимальное количество в пакетов в таком распределении.
Выходные данные
Выведите одно число — минимальное возможное количество пакетов, удовлетворяющие условию выше.
Примечание
В первом примере, три пакета с \(1\), \(2\) и \(3\) монетами могут быть использованы чтобы набрать любую сумму \(x\) (\(1\leq x\leq 6\)).
- Чтобы набрать \(1\) можно воспользоваться пакетом с \(1\) монетой.
- Чтобы набрать \(2\) можно воспользоваться пакетом с \(2\) монетой.
- Чтобы набрать \(3\) можно воспользоваться пакетом с \(3\) монетой.
- Чтобы набрать \(4\) можно воспользоваться пакетами с \(1\) и \(3\) монетами.
- Чтобы набрать \(5\) можно воспользоваться пакетами с \(2\) и \(3\) монетами.
- Чтобы набрать \(6\) можно воспользоваться всеми пакетами.
Во втором примере, два пакета с \(1\) и \(1\) монетами могут быть использованы чтобы набрать любую сумму \(x\) (\(1\leq x\leq 2\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
|
3
|
|
2
|
2
|
2
|