Công ty XYZ còn tồn đọng N sản phẩm từ năm ngoái, sản phẩm thứ i có chủng loại là c[i]. Do đặc thù kỹ thuật, các sản phẩm này không thể bán lẻ mà phải bán theo bộ 2 hoặc 3 sản phẩm cùng chủng loại.

Để giải quyết số hàng tồn đọng nhanh nhất có thể, công ty chia N sản phẩm này thành ít nhất có thể các bộ 2 hoặc 3 sản phẩm cùng chủng loại.

Yêu cầu: Hãy giúp công ty giải quyết công việc trên.

Dữ liệu ˆ

-Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 10^5 ) là số lượng sản phẩm tồn đọng. ˆ

-Dòng thứ hai chứa N số nguyên c[1], c[2], . . . , c[N] (1 ≤ c[i] ≤ 10^9 ) là chủng loại của các sản phẩm.

Kết quả ˆ

-In ra một số nguyên duy nhất là số bộ sản phẩm ít nhất có thể. Nếu không tồn tại cách chia, in ra −1.

Sample Input

10 
2 2 3 3 2 4 4 4 4 4

Sample Output

4

Sample Input

3
2 2 3

Sample Output

-1