E. Павел и треугольники
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Павла есть набор палок, с длинами равными степеням двойки.

У него есть $$$a_0$$$ палок длины $$$2^0 = 1$$$, $$$a_1$$$ палок длины $$$2^1 = 2$$$, ..., $$$a_{n-1}$$$ палок длины $$$2^{n-1}$$$.

Павел хочет составить из этих палок наибольшее количество треугольников, с площадью строго больше нуля, каждая палка при этом может содержаться не более чем в одном треугольнике.

Запрещено ломать палки, а также каждый треугольник должен состоять из ровно трех палок.

Найдеите наибольшее количество треугольников, которое может составить Павел.

Входные данные

Первая строка содержит единственное целое число $$$n$$$ — количество различных длин палок, которые есть у Павла ($$$1 \leq n \leq 300\,000$$$).

Вторая строка содержит $$$n$$$ целых чисел, разделенных пробелами, $$$a_0$$$, $$$a_1$$$, ..., $$$a_{n-1}$$$ ($$$1 \leq a_i \leq 10^9$$$), $$$a_i$$$ обозначает количество палок длины $$$2^i$$$.

Выходные данные

Выведите одно целое число — максимальное количество невырожденных треугольников, которые может составить Павел.

Примеры
Входные данные
5
1 2 2 2 2
Выходные данные
3
Входные данные
3
1 1 1
Выходные данные
0
Входные данные
3
3 3 3
Выходные данные
3
Примечание

В первом примере Павел может, например, составить такой комплект треугольников (перечислены длины сторон треугольника):

$$$(2^0, 2^4, 2^4)$$$, $$$(2^1, 2^3, 2^3)$$$, $$$(2^1, 2^2, 2^2)$$$.

Во втором примере Павел не может составить ни одного треугольника.

В третьем примере Павел может, например, составить такой комплект треугольников (перечислены длины сторон треугольника):

$$$(2^0, 2^0, 2^0)$$$, $$$(2^1, 2^1, 2^1)$$$, $$$(2^2, 2^2, 2^2)$$$.