An Internet user subscribes to various mailing lists, each dedicated to a specific topic, and receives emails accordingly. To manage these emails efficiently, the user has set up folders, each corresponding to one of the topics. Before reading the emails, the user organizes them by moving each message into its appropriate folder.
The email program on the user's computer allows the user to perform the following actions in a single "operation":
Move a single message from anywhere in the list of new messages.
Move a sequence of consecutive messages from the list, provided they all belong to the same topic.
Messages can be moved starting from any position in the "list of new messages." The goal is to transfer all new messages to their respective folders using the fewest number of operations possible.
For example, consider a user subscribed to newsletters on jokes, funny stories, sports news, and weather forecasts. Suppose the "list of new messages" at a certain time appears as follows: (Jokes, Sports News, Weather Forecast, Sports News, Funny Stories, Funny Stories, Sports News).
The user can organize the messages with these steps: first, move the two "Funny Stories" messages. The list then becomes: (Jokes, Sports News, Weather Forecast, Sports News, Sports News). Next, move the "Weather Forecast" message, followed by the "Jokes" message, and finally, move all three "Sports News" messages at once. This process takes a total of 4 operations.
Write a program to determine the minimum number of "operations" required to transfer all new messages into their respective folders. For simplicity, each topic is represented by a unique number.
Input
The input consists of a single line containing the number of new messages N (0 < N < 200) followed by N integers. Each integer represents the topic number of a message.
Output
Output the minimum number of operations needed for the given input data.