Trang trí

Marin và Josip vừa trở về sau buổi mua sắm Giáng sinh. Họ đã mua được một hộp gồm \(n\) món đồ trang trí cây thông. Các món đồ được xếp thành một hàng, và món đồ thứ \(i\) có màu \(a_i\).

Chiếc hộp được mở ở cả hai đầu và trong suốt, vì vậy Marin và Josip có thể nhìn thấy toàn bộ dãy màu sắc, và có thể lấy đồ từ đầu bên trái hoặc bên phải của hộp.

Josip nghĩ ra một trò chơi vui như sau:

• Hai người thay phiên nhau lấy đồ từ hộp, Marin đi trước.
• Mỗi lần chọn, người chơi có thể lấy món đồ ở đầu bên trái hoặc đầu bên phải.
• Nếu màu sắc của món đồ đó là màu chưa từng được lấy ra trước đó, người chơi đó sẽ ghi được \(1\) điểm.
• Trò chơi kết thúc khi tất cả món đồ đều đã được lấy ra.

Cả Marin và Josip đều là những người chơi tối ưu, họ sẽ luôn cố gắng đạt điểm số cao nhất có thể.

Hãy tính điểm số cuối cùng của mỗi người sau khi trò chơi kết thúc.

\InputFile

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 3000\)) --- số lượng món đồ trang trí.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) --- màu sắc của từng món đồ theo thứ tự từ trái sang phải.

\OutputFile

In ra hai số nguyên cách nhau bởi dấu hai chấm :, tương ứng là số điểm của Marin và Josip.

\Examples

\beginexample
\exmp4
1 2 1 2
1:1

\endexample

\Scoring

• Subtask 1 (17% số điểm): \(a_i \le 2\) với mọi \(i\)
• Subtask 2 (20% số điểm): \(n \le 20\)
• Subtask 3 (25% số điểm): \(n \le 300\)
• Subtask 4 (38% số điểm): Không giới hạn thêm

\endproblem