A Agustin le gustan mucho los juegos de puzzles y los speedruns. El siguiente juego de puzzle del que planea hacer un speedrun es el Zuma. En el Zuma hay una fila de \(N\) gemas, donde la gema en la posición \(i\) tiene el color \(C_i\). El objetivo del juego es destruir todas las gemas.

En un segundo Agustín puede elegir exactamente una subsecuencia continua de gemas de colores que sea un palíndromo y sacarla de la fila. Después de sacar esa subsecuencia, las gemas que quedan se juntan para volver a formar una fila continua, sin dejar huecos.

Para poder planear su speedrun Agustin quiere saber cual es la mínima cantidad de segundos que necesita para destruir todas las gemas

Una cadena (o subsecuencia) es un palíndromo si se lee exactamente igual de izquierda a derecha que de derecha a izquierda. En este caso particular, significa que el color de la primera gema tiene que ser igual al color de la última, el color de la segunda gema tiene que ser igual al de la anteúltima, y así sucesivamente.

Entrada

La primera línea de entrada tiene un solo número entero \(N\) (\(1 \leq N \leq 500\)), la cantidad total de gemas.

La segunda línea contiene N números enteros separados por un espacio, donde el número en la posición \(i\) es \(C_i\) (\(1 \leq C_i \leq N\)), que representa el color de la i-ésima gema en la fila.

Salida

Imprimí un único número entero que indique la cantidad mínima de segundos que se necesitan para destruir todas las gemas.

Ejemplos

Entrada 1

3
1 2 1

Salida 1

1

Entrada 2

3
1 2 3

Salida 2

3

Entrada 3

7
1 4 4 2 3 2 1

Salida 3

2