Giáng sinh là khoảng thời gian đẹp nhất trong năm. Hai anh em Wiliam và Jacica là hai diễn viên múa chính của đoàn nghệ thuật đỉnh cao số một thế giới. Các vở diễn của họ góp phần hồi sinh các giá trị đạo đức, văn hóa truyền thống, đem lại cho người xem năng lượng tích cực, cảm nhận sâu sắc về các giá trị tốt đẹp và sự bình yên trong tâm hồn. Wiliam và Jacica vừa trở về nhà sau chuyến lưu diễn vòng quanh thế giới và bắt đầu trang trí cây thông Noel của họ bằng những món đồ xinh xắn đã mua trong quá trình lưu diễn.

Họ đã mua \(n\) món đồ trang trí cây thông được xếp cạnh nhau trong một hộp dài, món đồ trang trí thứ \(i\) có màu A_i. Hộp được mở ở cả hai đầu, vì vậy các món đồ có thể được lấy ra từ bên trái hoặc bên phải của hộp. Hộp này trong suốt, nên Wiliam và Jacica có thể nhìn thấy màu sắc của từng món đồ trang trí.

Jacica nghĩ ra một trò chơi để việc trang trí cây thông trở nên thú vị hơn. Trò chơi diễn ra như sau: Wiliam và Jacica thay phiên nhau chơi, Wiliam là người bắt đầu. Người chơi trong lượt của mình sẽ lấy một món đồ trang trí từ hộp (có thể từ bên trái hoặc bên phải) và đặt nó lên cây thông. Nếu món đồ được lấy có màu chưa từng được người nào lấy trước đó, người chơi sẽ ghi được một điểm. Trò chơi kết thúc khi món đồ trang trí cuối cùng được lấy ra khỏi hộp.

Người chiến thắng là người ghi được nhiều điểm hơn. Vì cả Wiliam và Jacica đều là những người chơi xuất sắc, họ sẽ chơi một cách tối ưu.

Yêu cầu: Em hãy đưa ra kết quả cuối cùng của trò chơi.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq \ n \leq 3000)\) là số lượng món đồ trang trí trong hộp.

• Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\) \((1 \leq a_{i} \leq n)\) là màu sắc của món đồ thứ \(i\).

Kết quả: Ghi một dòng duy nhất gồm hai số, được nối bằng một ký tự “:” (dấu hai chấm), lần lượt là điểm số của Wiliam và Jacica.

Ví dụ:

Giải thích test ở ví dụ 1 Wiliam và Jacica có thể chơi theo cách sau:

Đầu tiên Wi	liam chọn món đồ có màu 1 ở bên trái và được 1 điểm.
Tiếp theo Ja	cica chọn món đồ có màu 1 ở bên phải và không có điểm vì màu 1 đã được lấy.
Tiếp theo Wi	liam chọn màu 1 ở vế bên trái và không được tăng thêm điểm vì màu 1 đã được lấy.
Tiếp theo J	acica lấy màu 2 ở vế bên trái và được 1 điểm vì màu 2 chưa từng được lấy.
Cuối cùng	Wiliam lấy màu 1 và không được tăng thêm điểm vì màu 1 đã được lấy.

Vậy kết quả cuối cùng ở ví dụ 1 là: 1:1

Giới hạn:

• Có 25% test với \(1 \leq \ a_{i}\ \leq \ 2\) với mọi i từ 1 đến \(n\);

• Có 20% test với \(1\ \leq \ n \leq \ 20\);

• Có 10% test với \(1 \leq \ a_{i} \leq 20\) với mọi i từ 1 đến \(n\);

• Có 20% test với \(1\ \leq \ \ n\ \leq \ 300\);

• Có 25% test với \(300\ < \ n\ \leq \ 3000\).