408940: GYM103385 3 Конструктор

Сереже на первое сентября подарили магнитный конструктор, состоящий из брусков разной длины, которые могут соединяться концами друг с другом. В подарочном наборе все бруски уложены в порядке неубывания длины, причем могут быть бруски одинаковой длины — это очень важно для Серёжи, потому что он собирается из брусков собирать равносторонние треугольники для своего большого проекта. Для этого проекта Серёже нужно очень много деталей в форме равносторонних треугольников, и он хочет понять, сколько всего он сможет собрать равносторонних треугольников из конструктора для последующего их одновременного использования в проекте. Определите, какое максимальное количество равносторонних треугольников можно собрать из конструктора (брусок, использованный в одном треугольнике, в другом уже использован быть не может).

В первой строке входных данных дано целое число $$$n$$$ — количество брусков ($$$1 \leq n \leq 10^5$$$). В следующих $$$n$$$ строках даны длины брусков конструктора — целые числа от 1 до $$$10^9$$$ по одному в строке. Числа даны в неубывающем порядке.

Требуется вывести одно целое число — максимально возможное число равносторонних треугольников.

Решения, правильно работающие при $$$n \leq 100$$$, будут оцениваться в 50 баллов.

6
1
1
1
1
2
2

1

6
1
1
3
3
5
5

0

В первом примере можно составить один треугольник из трёх брусков длины 1. Остались бруски длиной 1, 2, 2, из которых нельзя составить равносторонний треугольник.

Во втором примере нет трёх брусков равной длины, поэтому ни одного равностороннего треугольника составить нельзя.