Công ty của Khoa 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ể, sếp muốn Khoa 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.

Sau những ngày nghỉ Tết chỉ biết ăn và ngủ, đầu óc Khoa bây giờ không còn khả năng "nhảy số" nhanh nhẹn như trước nữa. Cậu chỉ biết nghĩ về những món ăn ngon mà mình đã ăn trong những ngày nghỉ Tết. Nhưng công việc sếp giao thì bắt buộc phải hoàn thành ngay hôm nay, nếu không sếp sẽ đuổi việc Khoa! Bị đuổi việc đầu năm quả là điều không may mắn chút nào.

Yêu cầu: Các bạn hãy giúp Khoa hoàn thành công việc sếp giao nhé.

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 3 3

Sample Output

-1