Pappu is an aspiring politician and he decides to follow PM's foot steps. So he began working at a tea stall.
At the end of the day there are total N tea cups, some of them are half filled and rest are empty. Pappu has to bring back all of them to the dishwasher. In each trip he brings back some of the cups. He can merge the contents of two half filled cups, and thus would be left with one full cup and an empty cup. He has to follow certain constraints, given below.
- He cannot put a (half/full) filled cup on any other cup. However, he can stack any number of empty cups together.
- He cannot put any cup on a (half/full) filled cup.
Pappu is entertaining but not that smart. You have to help him to find out minimum number of trips required to bring back all the cups.
INPUT :
The first line of the input contains a single integer N.
The Second line of the input contains N space separated integers. Each integer is either 0 or 1 .
Integer 0 represents an empty cup and 1 represents an half-filled cup.
OUTPUT:
Print out a single integer which is equal to the minimum number of trips required for pappu to bring all the N tea cups to the dishwasher.
CONSTRAINTS:
1 ≤ N ≤ 100
Each integer is either 0 or 1
There are a total of 5 tea cups.
out of them 2 cups are empty and 3 cups are half -filled.
The two empty cups can be stacked together.
Two half-filled cups can be made into one full cup and one empty cup. This empty cup can be stacked along with the previous two empty cups.
Now, there is one full cup, one half-filled cup and one stack of empty cups.
Therefore, pappu needs two trips to get the cups to the dish-washer (in one trip he can bring one full cup using one hand and one half-filled cup using the other hand. In the second trip he can bring the stack of empty cups using one hand).
