Find Minimum Trips

Each trip must deliver exactly 2 or 3 packages of the same weight, and every package must be delivered exactly once. Find the minimum number of trips, or output -1 if it cannot be done.

输入格式

The first line contains n; the second line contains the weights. Weights are in 1..10^9. The original upper bound on n had an extra trailing character 5; this site explicitly uses 1≤n≤100000 and does not treat the typesetting damage as a new order of magnitude.

输出格式

Output a single integer, the answer.

样例 1

输入：

5
1 1 1 2 2

输出：

2

样例 2

输入：

1
1

输出：

-1

样例 3

输入：

4
5 5 5 5

输出：

2

样例说明

Example 1: the three packages of weight 1 go in one trip and the two of weight 2 in another, 2 trips in total. Example 2: a single package cannot form a group of 2 or 3, so there is no solution: -1. Example 3: the 4 packages split into two groups of 2, which takes 2 trips.