| Codeforces Round 609 (Div. 1) |
|---|
| Закончено |
Вам дана диаграмма Юнга.
Данная диаграмма это гистограмма с $$$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$$$.
В первой строке записано одно целое число $$$n$$$ ($$$1 \leq n \leq 300\,000$$$): количество столбцов в данной гистограмме.
В следующей строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 300\,000, a_i \geq a_{i+1}$$$): длины столбцов.
Выведите одно целое число: наибольшее количество непересекающихся домино, которое вы можете нарисовать внутри данной диаграммы Юнга.
5 3 2 2 2 1
4
Некоторые возможные решения для первого примера:
