G. Большие букеты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В цветочный магазин привезли n букетов, причем i-й букет состоит из ai цветов. Продавец Вася решил сделать из имеющихся букетов большие букеты.

Под большим букетом Вася понимает букет, составленный из двух или более привезенных букетов, причем количество цветов в большом букете обязательно должно быть нечетным. Каждый из привезенных букетов может стать частью не более одного большого букета. Если привезенный букет выбирается для составления большого букета, то все цветы, которые есть в нем, обязательно берутся в большой букет.

Определите максимальное количество больших букетов, которые может составить Вася.

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

В первой строке следует целое положительное число n (1 ≤ n ≤ 105) — количество привезенных букетов.

Во второй строке следует последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — количество цветов в каждом из привезенных букетов.

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

Выведите максимальное количество больших букетов, которые может составить Вася.

Примеры
Входные данные
5
2 3 4 2 7
Выходные данные
2
Входные данные
6
2 2 6 8 6 12
Выходные данные
0
Входные данные
3
11 4 10
Выходные данные
1
Примечание

В первом примере можно составить 2 больших букета. Например, в первый большой букет можно взять первый и пятый привезенные букеты (суммарное количество цветов будет равно 9), а во второй большой букет — второй и третий привезенные букеты (суммарное количество цветов будет равно 7). Четвертый привезенный букет останется неиспользованным.

Во втором примере невозможно составить ни одного большого букета, который бы состоял из нечетного количества цветов.

В третьем примере можно составить один большой букет. Например, это можно сделать, взяв все три привезенных букета. Размер этого большого букета будет равен 11 + 4 + 10 = 25.