favorite We need a little bit of your help to keep things running, click on this banner to learn more

Dynamic programming


Boyan is playing a computer game. In the beginning there are n balls arranged in a line. Each ball has a number written on it, so that every two consecutive balls have different numbers. The game consists of the following steps:

  1. The player removes a ball from the line.

  2. While there are consecutive balls with equal numbers, they are automatically removed from the line.

  3. If there are balls left in the line, go to step 1, otherwise the game ends.

The score is the number of balls that are automatically removed. The goal of the game is to maximize the score.

  1. Boyan removes the ball with number 3. The balls left are {1, 2, 2, 1, 5}.

  2. Removing the consecutive balls with equal numbers we have {1, 2, 2, 1, 5} -> {1, 1, 5} -> {5}. The ball left is {5}.

  3. Since there are balls left, we go to step 1.

Next iteration:

  1. Boyan removes the ball with number 5. The balls left are {}.

  2. There are no consecutive balls with equal numbers.

  3. There are no balls left, so the game ends.

The number of balls that are automatically removed is 4. It is the maximum possible score for this game. Boyan is playing a lot, but he is still not sure when he is playing optimally. Write program game to help him to find the best score he can achieve.


The first line contains the positive integer n (1n500). The second line contains n positive integers - the numbers written on the balls (number on a ball ≤ 106).


Print the maximum possible score Boyan can achieve.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1 2 3 2 1 5
Output example #1
Input example #2
1 5 1 3 2 4 2 3 1
Output example #2
Source 2017 IX International autumn tournament in informatics, Shumen, Junior, Problem B