Genos gần đây đã cài đặt trò chơi Zuma trên điện thoại của mình. Trong trò chơi Zuma, có một hàng gồm \(n\) viên đá quý, viên thứ \(i\) có màu \(c_i\). Mục tiêu của trò chơi là tiêu diệt tất cả các viên đá quý trong hàng càng nhanh càng tốt.

Trong một giây, Genos có thể chọn một đoạn con liên tiếp các viên đá quý tạo thành một chuỗi đối xứng (palindrome) và loại bỏ nó khỏi hàng. Sau khi đoạn con bị loại bỏ, các viên đá quý còn lại sẽ dịch chuyển để tạo thành một hàng liên tục. Số giây tối thiểu cần thiết để tiêu diệt toàn bộ hàng là bao nhiêu?

Nhắc lại rằng, một chuỗi (hoặc đoạn con) được gọi là đối xứng nếu nó đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Như vậy, đoạn đối xứng trong hợp này sẽ có màu của viên đá quý đầu tiên bằng màu của viên cuối cùng, màu của viên thứ hai bằng màu của viên kế cuối, và cứ tiếp tục như vậy.

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(n\) (\(1 \le n \le 500\)) — số lượng viên đá quý.
• Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách, số thứ \(i\) là \(c_i\) (\(1 \le c_i \le n\)) — màu của viên đá quý thứ \(i\) trong hàng.

Output

• In ra một số nguyên duy nhất — số giây tối thiểu cần thiết để tiêu diệt toàn bộ hàng.

Example

3
1 2 1

1

3
1 2 3

3

7
1 4 4 2 3 2 1

2

Nguồn: - Codeforces 607B