Satan và Claus dự định trang trí cây thông bằng các bóng đèn đầy màu sắc. Có ~n~ bóng đèn được sắp xếp thành hàng ngang trong một chiếc hộp, bóng đèn thứ ~i~ có màu ~a_i~, một số bóng đèn có thể trùng màu với nhau. Chiếc hộp được mở ở cả hai đầu, vì vậy có thể lấy bóng đèn ở cả hai phía trái hoặc phải. Ngoài ra, chiếc hộp trong suốt nên Satan và Claus có thể nhìn rõ màu sắc của từng bóng đèn ở bên trong.

Trong lúc trang trí, Satan và Claus nghĩ ra một trò chơi thú vị. Trò chơi diễn ra như sau: Ban đầu Satan là người bắt đầu và cả hai thực hiện lượt chơi luân phiên. Ở mỗi lượt, người chơi có thể lấy ra một bóng đèn từ phía bên trái hoặc phải chiếc hộp và treo nó lên cây. Nếu người đó treo lên một bóng đèn có màu sắc mới sẽ được ~1~ điểm, ngược lại nếu treo bóng đèn có màu sắc trùng với bóng đèn đã được treo sẽ không có điểm. Trò chơi kết thúc khi toàn bộ ~n~ bóng đèn đều được treo trên cây.

Hình ảnh minh họa các bóng đèn ở ví dụ thứ hai. Trong lượt chơi đầu tiên, Satan có thể lấy bóng đèn có màu sắc ~1~ ở bên trái hoặc màu sắc ~3~ ở bên phải

Giả sử rằng cả Satan và Claus đều nghĩ ra được cách chơi tối ưu. Hãy xác định số điểm mà mỗi người chơi có được sau khi trò chơi kết thúc.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 3000)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le n)~.

Output

• In ra hai số nguyên là số điểm mà Satan và Claus đạt được sau khi trò chơi kết thúc, ngăn cách nhau bởi dấu hai chấm.

Samples

Sample Input 1

5
1 1 2 1 1

Sample Output 1

1:1

Sample Input 2

6
1 2 3 1 2 3

Sample Output 2

2:1

Scoring

• Subtask ~1~ với ~15\%~ số điểm: ~a_i \le 2~ với mọi ~1 \le i \le n~
• Subtask ~2~ với ~18\%~ số điểm: ~n \le 20~
• Subtask ~3~ với ~28\%~ số điểm: ~a_i \le 20~ với mọi ~1 \le i \le n~
• Subtask ~4~ với ~20\%~ số điểm: ~n \le 300~
• Subtask ~5~ với ~19\%~ số điểm: Không có ràng buộc gì thêm

Clarification

Hình sau mô tả các lượt chơi ở ví dụ đầu tiên:

• Ở lượt đầu tiên, Satan lấy bóng đèn màu ~1~ ở bên trái, treo lên cây và có được ~1~ điểm.
• Ở lượt thứ hai, Claus lấy bóng đèn màu ~1~ ở bên phải, tuy nhiên bóng đèn màu ~1~ đã được treo nên không có điểm nào.
• Ở lượt thứ ba, Satan lấy bóng đèn màu ~1~ ở bên trái, tuy nhiên bóng đèn màu ~1~ đã được treo nên không có điểm nào.
• Ở lượt thứ tư, Claus lấy bóng đèn màu ~2~ ở bên trái, treo lên cây và có được ~1~ điểm.
• Ở lượt cuối cùng, Satan lấy bóng đèn màu ~1~ ở bên trái, tuy nhiên bóng đèn màu ~1~ đã được treo nên không có điểm nào.

Sau khi kết thúc trò chơi, cả Satan và Claus đều có được ~1~ điểm và kết quả là ~1:1~.