Giáng sinh đang đến gần, thời điểm đẹp nhất trong năm. Nhân vật chính của chúng ta, Marin và Josip, đã trở về sau chuyến mua sắm Giáng sinh và bắt đầu trang trí cây thông Noel của họ.

Họ mua ~n~ đồ trang trí Giáng sinh được xếp cạnh nhau trong một hộp dài và đồ trang trí thứ ~i~ có màu ~a_i~. Hộp mở được cả hai mặt nên có thể lấy đồ trang trí ra từ cả bên trái và bên phải của hộp. Chiếc hộp trong suốt nên Marin và Josip có thể nhìn thấy màu sắc của từng vật trang trí.

Hình minh họa cho thấy trạng thái ban đầu của hộp trong ví dụ thứ hai. Trong lần đi đầu tiên, Marin có thể lấy vật trang trí màu ~1~ từ đầu bên trái của hộp hoặc vật trang trí màu ~3~ từ đầu bên phải của hộp.

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

Người chiến thắng trong trò chơi là người chơi ghi được nhiều điểm hơn nên cả Marin và Josip đều muốn tối đa hóa số điểm của mình. Vì cả hai đều là những cầu thủ xuất sắc nên họ sẽ chơi một cách tối ưu. Nhiệm vụ của bạn là đưa ra kết quả khi kết thúc trò chơi.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ (~1 \leq n \leq 3000~) là số đồ trang trí.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~1 \leq a_i \leq n~) là màu của các đồ trang trí.

Output

Trên một dòng duy nhất, đưa ra kết quả của trò chơi, tức là hai số kết nối bởi kí tự : lần lượt là điểm số của Marin và Josip.

Scoring

1. ~a_i \leq 2 \space \forall i = 1, 2, ..., n~ (17 điểm)

2. ~n \leq 20~ (10 điểm)

3. ~a_i \leq 20 \space \forall i = 1, 2, ..., n~ (26 điểm)

4. ~n \leq 300~ (15 điểm)

5. Không có ràng buộc gì thêm (42 điểm)

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

Explanation

Ở ví dụ đầu tiên:

• Marin là người đầu tiên và anh ấy rút một vật trang trí màu ~1~ từ đầu bên trái của hộp. Marin ghi được một điểm.
• Josip rút một vật trang trí màu ~1~ từ đầu bên phải của hộp, nhưng anh ấy không ghi được điểm vì một vật trang trí màu ~1~ đã được rút ra.
• Marin rút một vật trang trí màu ~1~ từ đầu bên trái của hộp. Anh ta cũng không ghi được điểm nào vì một vật trang trí màu ~1~ đã được rút ra.
• Josip vẽ một vật trang trí màu ~2~ từ đầu bên trái của hộp. Đây là quả bóng màu ~2~ đầu tiên được rút ra nên Josip ghi được một điểm.
• Marin rút vật trang trí cuối cùng (màu ~1~) từ đầu bên trái của hộp, nhưng nó không mang lại cho anh ta điểm và trò chơi kết thúc.

Marin có tổng cộng ~1~ điểm (anh ấy rút đồ trang trí màu ~1~ trước), và Josip cũng có tổng điểm ~1~ (anh ấy rút đồ trang trí màu ~2~ trước). Kết quả cuối cùng là ~1~:~1~.