Вам дана диаграмма Юнга.
Данная диаграмма это гистограмма с \(n\) столбцами длин \(a_1, a_2, \ldots, a_n\) (\(a_1 \geq a_2 \geq \ldots \geq a_n \geq 1\)).
Диаграмма Юнга для \(a=[3,2,2,2,1]\). Ваша задача — найти наибольшее количество непересекающихся домино, которое вы можете нарисовать внутри этой диаграммы, домино это прямоугольник \(1 \times 2\) или \(2 \times 1\).
Выходные данные
Выведите одно целое число: наибольшее количество непересекающихся домино, которое вы можете нарисовать внутри данной диаграммы Юнга.
Примечание
Некоторые возможные решения для первого примера:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 2 2 2 1
|
4
|