Sơn hàng rào

Một hàng rào gồm $n$ tấm ván xếp thành một hàng, đánh số từ $1$ đến $n$ từ trái sang phải. Ban đầu các tấm ván chưa được sơn. Người thợ cần sơn để tấm ván thứ $i$ có màu $s_i$, trong đó mỗi màu được kí hiệu bằng một chữ cái Latin thường.

Mỗi lượt sơn, người thợ chọn một đoạn các tấm ván liên tiếp và một màu, rồi sơn toàn bộ đoạn đó bằng màu này; màu mới phủ lên mọi màu cũ trên đoạn.

Yêu cầu: Tính số lượt sơn ít nhất để hàng rào có đúng các màu $s_1,s_2,\dots ,s_n$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa xâu $s$ gồm $n$ chữ cái Latin thường.

Dữ liệu ra

In một số nguyên duy nhất là số lượt sơn ít nhất.

Ràng buộc

• $1\le n\le 500$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 15$.
• Subtask 2 ($30\%$ số điểm): xâu $s$ có không quá hai chữ cái khác nhau.
• Subtask 3 ($40\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ