Matryoshka Dolls

Time limit5sMemory limit128 MB

Summary

Reassemble a row of dolls into complete 1 to m sets using adjacent merges while minimizing the number of doll openings.

Level: Hard8 of 10
Topics: Dynamic programming, Intervals
Solved: No attempts yet

Problem

A matryoshka is a traditional Russian wooden doll that holds a series of ever-smaller dolls nested inside it. When you open a matryoshka, there is a smaller doll inside; open that one and there is an even smaller doll inside it, and so on until you reach a doll with nothing inside.

A museum put together an exhibit of several matryoshka sets that all look alike but contain different numbers of dolls. Some children then took every set apart and lined up all the dolls in a single row. There are now $n$ dolls standing in a row (each doll's size is an integer), and no one knows how many sets there originally were or how many dolls each set contained. The only certainty is that the sizes of the dolls in one complete matryoshka set are always the consecutive integers from $1$ up to some integer $m$ . The value of $m$ may differ from set to set.

You must reassemble the dolls in the row back into complete sets, following these rules:

A larger doll cannot be placed inside a smaller doll.
To combine two groups (partially assembled bundles of dolls), the two groups must be adjacent in the row.
Once a doll has been placed into a group, it cannot be moved to another group or taken out on its own, except when that group is combined with another group.

The longer the work takes, the worse it is, so you must minimize the number of times a doll is opened. Only the time to open and close dolls matters, so it is enough to minimize the number of openings. For example, combining group $[1, 2, 6]$ with group $[4]$ requires a minimum of $2$ openings, because the dolls of size $6$ and size $4$ must be opened. Combining group $[1, 2, 5]$ with group $[3, 4]$ requires a minimum of $3$ openings.

Compute the minimum number of doll openings needed to reassemble the disassembled matryoshkas back into complete sets.

Input

The first line contains the number of dolls in the row, $n$ ( $1 \le n \le 500$ ).

The second line contains the sizes of the dolls in the order they stand in the row, separated by spaces. Each size is an integer between $1$ and $500$ , inclusive.

Output

Print the minimum number of doll openings needed to reassemble the dolls into complete matryoshka sets. If reassembly is impossible (some dolls may have been stolen), print impossible.

Examples4

Example 1
Input
```
7
1 2 3 2 4 1 3
```
Expected output
```
7
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
2
2 1
```
Expected output
```
1
```
Example 4
Input
```
3
1 2 3
```
Expected output
```
2
```