Problem Description

Takashi, who loves skiing, started a part-time job as a lift operator at the Nico Nico Ski Resort. The resort has one lift with a capacity of 4 people per chair, and skiers come in groups of 1 to 4 people.

One day, Takashi was troubled by a long queue for the lift and decided to ask the skiers to share the lift chairs. Takashi decided to guide the groups of skiers to the chairs following these steps each time a chair arrives at the loading area:

• First, guide the group at the front of the queue to the chair.
• As long as there are groups that can join the current chair without exceeding the capacity, guide such groups to the chair. However, if there are multiple such groups, it is acceptable to guide any of them, regardless of their position in the queue.

Currently, there are $ N $ groups of skiers waiting for the lift, and the $i\ (1 \leq i \leq N)$th group from the front of the queue consists of $ A_i $ skiers. Determine the minimum number of chairs needed to transport all the groups waiting in the queue.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ A_2 $ $ : $ $ A_N $

Output Format

Output the number of chairs needed to transport all the waiting groups in one line. Ensure to end the output with a newline.

Sample Input and Output

Sample Input #1

3
1
1
2

Sample Output #1

1

Sample Input #2

6
3
1
4
2
1
2

Sample Output #2

4

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 4$

Sample Explanation 1

As long as the total is within 4 people, Takashi can guide any number of groups to the same chair.

Sample Explanation 2

For example, by guiding the skiers as follows, all groups can be transported using 4 chairs:
- Guide the 1st and 5th groups to the 1st chair.
- Guide the 2nd and 4th groups to the 2nd chair.
- Guide the 3rd group to the 3rd chair.
- Guide the 6th group to the 4th chair.

见题面 Input 部分

见题面 Output 部分