Lễ hội mùa đông đang đến gần, và trong không khí rộn ràng ấy, hai chị em Minh và An đã trở về sau buổi mua sắm đồ trang trí. Họ mang về một chiếc hộp dài chứa \(n\) quả cầu trang trí xếp thành hàng.
Chiếc hộp đặc biệt này mở ở cả hai đầu, cho phép Minh và An có thể lấy quả cầu từ bên trái hoặc bên phải. Vì chiếc hộp làm bằng kính trong suốt, cả hai có thể nhìn thấy màu sắc của từng quả cầu.
An nảy ra một trò chơi nhỏ để việc trang trí thêm phần thú vị: Minh và An sẽ thay phiên nhau lấy quả cầu từ hộp (chọn lấy ở đầu trái hoặc đầu phải) và treo lên cây. Minh sẽ là người đi trước.
Luật chơi như sau: nếu người chơi lấy được một quả cầu có màu sắc chưa từng được lấy ra trước đó, người đó sẽ ghi được \(1\) điểm. Trò chơi kết thúc khi quả cầu cuối cùng được lấy ra khỏi hộp.
Cả Minh và An đều muốn giành chiến thắng, nên họ sẽ chơi một cách tối ưu. Nhiệm vụ của bạn là xác định số điểm cuối cùng của mỗi người sau khi trò chơi kết thúc.
Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 3000\)) --- số quả cầu trong hộp.
Dòng thứ hai chứa \(n\) số nguyên \(a_i\) (\(1 \le a_i \le n\)) --- màu sắc của quả cầu thứ \(i\) (biểu diễn bởi một số nguyên).
Output
In ra một dòng duy nhất hai số nguyên là điểm số của Minh và An, ngăn cách nhau bởi dấu ':' (dấu hai chấm). Minh đi trước.
Example
Test 1
Input
5
1 1 2 1 1
Output
1:1
Test 2
Input
6
1 2 3 1 2 3
Output
2:1
Scoring
- Subtask 1 (17 điểm): \(a_i \le 2\) với mọi \(i = 1, 2, \ldots, n\)
- Subtask 2 (10 điểm): \(n \le 20\)
- Subtask 3 (26 điểm): \(a_i \le 20\) với mọi \(i = 1, 2, \ldots, n\)
- Subtask 4 (15 điểm): \(n \le 300\)
- Subtask 5 (32 điểm): Không có ràng buộc bổ sung
