Compartments

题意翻译

**题目描述:** 一支来自$S$市的学生队伍被派去参加柏林信息学奥林匹克竞赛。他们乘火车去到那里,所有学生都买了一节车厢的票,车厢由$n$个隔间组成(每个车厢正好有4个人)。我们知道,如果一个隔间里只有一两个学生,那么他们会感到无聊;如果一个包厢里有三到四个学生,那么这个包厢在整个旅程中都会欢歌笑语。 同学们都想和别人交换,这样就没有一个隔间里的学生会无聊了。要想和另一个人交换位置,你需要让他相信这是很必要的。学生们无法独立地找到必要的论据,所以他们向一位富有同情心的售票员寻求帮忙。售票员可以用她的生活经验说服任何乘客跟任何学生交换位置。 然而,售票员不想浪费时间去说服不用换位的人,所以她想知道说服乘客和学生换位所需的最少次数是多少。你的任务是找到这个**最小次数**。 在所有的换座完了之后,每个隔间要么没有学生,要么有三四个学生。 **输入格式:** 第一行输入一个数$n$,表示包厢里有多少个隔间。($n$<=$10^6$) 第$2$行输入$n$个数:$a_1$~$a_n$,每个数代表着每个隔间里有多少学生。保证包厢内至少有一个学生。($0$<=$a_i$<=$4$) **输出格式:** 如果没有与其他人交换座位的方法使得最终结果符合题意,**请输出数字:“$-1$”(不带引号)。** 如果可以,**输出你需要说服交换位置的最少人数**。

题目描述

A team of students from the city S is sent to the All-Berland Olympiad in Informatics. Traditionally, they go on the train. All students have bought tickets in one carriage, consisting of $ n $ compartments (each compartment has exactly four people). We know that if one compartment contain one or two students, then they get bored, and if one compartment contain three or four students, then the compartment has fun throughout the entire trip. The students want to swap with other people, so that no compartment with students had bored students. To swap places with another person, you need to convince him that it is really necessary. The students can not independently find the necessary arguments, so they asked a sympathetic conductor for help. The conductor can use her life experience to persuade any passenger to switch places with some student. However, the conductor does not want to waste time persuading the wrong people, so she wants to know what is the minimum number of people necessary to persuade her to change places with the students. Your task is to find the number. After all the swaps each compartment should either have no student left, or have a company of three or four students.

输入输出格式

输入格式


The first line contains integer $ n $ ( $ 1<=n<=10^{6} $ ) — the number of compartments in the carriage. The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ showing how many students ride in each compartment ( $ 0<=a_{i}<=4 $ ). It is guaranteed that at least one student is riding in the train.

输出格式


If no sequence of swapping seats with other people leads to the desired result, print number "-1" (without the quotes). In another case, print the smallest number of people you need to persuade to swap places.

输入输出样例

输入样例 #1

5
1 2 2 4 3

输出样例 #1

2

输入样例 #2

3
4 1 1

输出样例 #2

2

输入样例 #3

4
0 3 0 4

输出样例 #3

0