Minimizing Openings in Matryoshka Reassembly

The Russian Matryoshka Museum displays sets of traditional nested dolls. Each complete matryoshka set is a sequence of dolls with consecutive sizes from 1 up to some number m (i.e. the complete set is {1,2,…,m}). Due to mischievous children, the dolls from several complete sets have been taken out and placed in a row. Your task is to reassemble the complete sets following these rules:

• You may combine two adjacent groups only by nesting one group into a doll from the other group. (Recall that a doll can enclose a doll or an already nested group only if it is larger.)
• Each complete set must eventually consist of dolls whose sizes, when sorted, are exactly 1, 2, …, m (for some m that may differ among sets).
• The only time‐consuming operation is opening (and subsequently closing) a doll. When merging two groups, you must open the outer doll of each group that is directly involved in the merge. For example, merging the groups [1,2,6] and [4] requires opening the dolls of size 6 and 4 (total cost 2), whereas merging [1,2,5] and [3,4] requires opening three dolls.

Given the row of n dolls (each represented by an integer size), compute the minimum number of openings required to reassemble all the disassembled matryoshka sets. It is guaranteed that the dolls come from complete sets (although the sizes and the number of dolls in each set may vary).

Note: The process of reassembly involves only combining adjacent groups. Once dolls are merged into a group, they cannot be separated again (except for the temporary openings needed during a merge).

inputFormat

The first line contains an integer n (1 ≤ n ≤ 300), the number of dolls in the row. The second line contains n integers separated by spaces. Each integer represents the size of a doll. It is guaranteed that these dolls originally came from one or more complete matryoshka sets (each complete set consists of dolls of consecutive sizes starting from 1).

outputFormat

Output a single integer — the minimum number of doll openings required to reassemble the complete matryoshka sets.

sample

4
1 2 6 4

2