An vừa mới lập trình một trò chơi trên máy tính như sau: Trên màn hình máy tính An cho hiễn thị một dãy N ô, mỗi ô chứa một số nguyên. Mỗi lượt chơi, người chơi chọn một dãy con các ô liên tục của dãy hiện tại để tách ra khỏi dãy. Để trò chơi thêm tính trí tuệ, An quy định chỉ tách được dãy con nếu dãy đó là dãy đối xứng (khi đọc giá trị trong các ô từ trái qua phải giống như đọc từ phải qua trái). Sau khi tách một dãy con thì các ô còn lại sẽ tự động dịch lại sát nhau. Trò chơi kết thúc khi tách hết tất cả các ô trong dãy ban đầu. Bạn hãy viết chương trình tính xem cần ít nhất bao nhiêu lượt chơi để tách hết tất cả các ô trong dãy ban đầu.

Dữ liệu vào:

• Dòng đầu tiên ghi số N là số lượng ô trong dãy ban đầu ~(1 ≤ N ≤ 5.10^2)~
• Dòng tiếp theo ghi N số nguyên ~A_1~,~A_2~,…,~A_N~ lần lượt là giá trị trong các ô của dãy (1 ≤ ~A_i~ ≤ ~10^9~).

Dữ liệu ra:

• Là số lượt chơi ít nhất tìm được.

Ví dụ:

INP 1

4
2 4 6 3

OUT 1

4

Giải thích

• Cần ít nhất 4 lượt chơi, mỗi lượt chỉ tách được một ô

INP 2

7
2 5 5 3 17 3 2

OUT 2

2

Giải thích

• Lượt chơi thứ nhất tách hai ô 5 5, dãy còn lại là 2 3 17 3 2
• Lượt chơi thứ hai tách năm ô 2 3 17 3 2 Hoặc
• Lượt chơi thứ nhất tách ba ô 3 17 3, dãy còn lại là 2 5 5 2
• Lượt chơi thứ hai tách bốn ô 2 5 5 2