У пингвина Rocher есть \(n\) палочек — у него ровно одна палочка длины \(i\) для всех \(1 \le i \le n\).
Он может соединять некоторые палочки. Если он соединяет две палочки, которые имеют длины \(a\) и \(b\), он получает одну палочку длины \(a + b\). Две палочки, которые были использованы в этой операции, пропадают из его множества. Новая соединенная палочка появляется в его множестве и может быть использована в следующих соединениях.
Он хочет создать максимальное количество палочек, имеющих одинаковую длину. Не обязательно при этом, чтобы в итоге все палочки имели одинаковую длину — некоторые палочки могут иметь другие длины. Какое максимальное количество палочек одинаковой длины он может получить в итоге?
Выходные данные
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
Примечание
В третьем наборе входных данных он может соединить две палочки длины \(1\) и \(2\) и он получит одну палочку длины \(3\). Так он получит две палочки одинаковой длины \(3\).
В четвертом наборе входных данных он может соединить две палочки длины \(1\) и \(3\) и он получит одну палочку длины \(4\). После этого у него будет три палочки, имеющие длины \(\{2, 4, 4\}\). Две палочки имеют одинаковую длину и она палочка будет иметь другую длину.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
2
3
4
|
1
1
2
2
|