← 返回题目列表

Codeforces · 356/C

C. 隔间

中文机器翻译题面 查看原题

S市的学生代表队被派往全伯兰信息学奥林匹克竞赛。按照传统,他们会坐火车。所有学生都买了一辆车厢的票,车厢有 n 个车厢(每个车厢正好有四个人)。我们知道,如果一个车厢容纳一两个学生,那么他们会感到无聊,而如果一个车厢容纳三到四个学生,那么整个车厢就会充满乐趣。

学生想与其他人交换,这样没有车厢的学生就感到无聊了。想要和另一个人交换位置,你需要让他相信这确实有必要。学生们无法独立找到必要的论据,所以他们向一位富有同情心的指挥寻求帮助。售票员可以利用她的生活经验说服任何乘客与某个学生交换位置。

然而,售票员不想浪费时间说服错误的人,所以她想知道说服她与学生交换位置所需的最少人数是多少。你的任务是找到这个号码。

在所有交换之后,每个隔间应该没有学生留下,或者有三到四名学生。

输入

第一行包含整数 n (1 ≤ n ≤ 106) — 车厢的车厢数。第二行包含n个整数a1,a2,...,an表示每个车厢有多少个学生乘坐(0≤ai≤4)。保证至少有一名学生乘坐火车。

输出

如果与其他人交换座位的顺序没有达到预期的结果,则打印数字“-1”(不带引号)。在另一种情况下,请打印出您需要说服交换位置的最少人数。

示例

输入 #1

5
1 2 2 4 3

输出 #1

2

输入 #2

3
4 1 1

输出 #2

2

输入 #3

4
0 3 0 4

输出 #3

0