水果礼盒

题目描述

水果批发市场有 $n$ 个水果，种类分别为 $f_1, f_2, \dots, f_n$。你每次可以选择2个或3个同种类的水果打包成一个礼盒。请问最少需要打包多少次才能将所有水果打包？如果无法全部打包，请输出-1。

输入格式

第一行一个整数 $n$，表示水果个数， 第二行 $n$ 个整数 $f_1, f_2, \dots, f_n$，表示每个水果的种类。

输出格式

最少需要的打包次数，若无法完成输出-1

样例

输入样例1

5
1 1 1 2 2

输出样例1

2

解释：第一次打包3个1类水果，第二次打包2个2类水果

输入样例2

4
1 1 2 3

输出样例2

-1

解释：2类和3类水果数量不足，无法打包

数据范围

• 30%数据：$n \leq 100$，只有1-2种水果 • 30%数据：所有水果种类相同 • 100%数据：$n \leq 2 \times 10^5$，$1 \leq f_i \leq 10^5$