Description

Scanffer is a student who enjoys playing Minecraft. As we all know, in Minecraft, players can obtain various types of logs, such as oak logs, spruce logs, jungle logs, etc. Each type of log corresponds to a specific type of plank, such as oak plank, spruce plank, jungle plank, etc.

In the crafting system of Minecraft, any $2$ planks can be crafted into $4$ sticks (the types of the $2$ planks can be different), and $2$ sticks and $4$ planks of the same type can be crafted into $3$ fences.

Now, assume there are $n$ types of planks in Minecraft, and Scanffer has $a_i$ planks of the $i$-th type. Scanffer wants to craft the maximum number of fences using these wooden planks. Please output the maximum number of fences that can be crafted.

Input

The first line contains a single integer $n$ ($1 \le n \le 2 \times 10^5$), the number of plank types.

The second line contains $n$ integers $a_1,a_2,\ldots ,a_n$ ($0 \le a_i \le 1000$), where $a_i$ is the number of planks of the $i$-th type that Scanffer has.

Output

Print a single integer: the maximum number of fences that can be crafted.

Samples

2
4 2

3

4
6 4 4 6

12

Note

In the first test case, Scanffer can use all the planks of the second type to craft into $4$ sticks. Then use the $4$ planks of the first type and two sticks to craft $3$ fences.

In the second test case, use $2$ planks of the first type and $2$ planks of the fourth type to craft into sticks. Then use all the rest of the planks to craft fences.

Resources

电子科技大学第十五届 ACM 趣味程序设计竞赛