У Павла есть набор палок, с длинами равными степеням двойки.
У него есть \(a_0\) палок длины \(2^0 = 1\), \(a_1\) палок длины \(2^1 = 2\), ..., \(a_{n-1}\) палок длины \(2^{n-1}\).
Павел хочет составить из этих палок наибольшее количество треугольников, с площадью строго больше нуля, каждая палка при этом может содержаться не более чем в одном треугольнике.
Запрещено ломать палки, а также каждый треугольник должен состоять из ровно трех палок.
Найдеите наибольшее количество треугольников, которое может составить Павел.
Выходные данные
Выведите одно целое число — максимальное количество невырожденных треугольников, которые может составить Павел.
Примечание
В первом примере Павел может, например, составить такой комплект треугольников (перечислены длины сторон треугольника):
\((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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 2 2 2
|
3
|
|
2
|
3
1 1 1
|
0
|
|
3
|
3
3 3 3
|
3
|