题目背景

题目描述

Matryoshkas are sets of traditional Russian wooden dolls of decreasing size placed one inside the other. A matryoshka doll can be opened to reveal a smaller figure of the same sort inside, which has, in turn, another figure inside, and so on.

The Russian Matryoshka Museum recently exhibited a collection of similarly designed matryoshka sets, differing only in the number of nested dolls in each set. Unfortunately, some over-zealous (and obviously unsupervised) children separated these sets, placing all the individual dolls in a row. There are $n$ dolls in the row, each with an integer size. You need to reassemble the matryoshka sets, knowing neither the number of sets nor the number of dolls in each set. You know only that every complete set consists of dolls with consecutive sizes from $1$ to some number $m$, which may vary between the different sets.

When reassembling the sets, you must follow these rules:

• You can put a doll or a nested group of dolls only inside a larger doll.
• You can combine two groups of dolls only if they are adjacent in the row.
• Once a doll becomes a member of a group, it cannot be transferred to another group or permanently separated from the group. It can be temporarily separated only when combining two groups.

Your time is valuable, and you want to do this reassembly process as quickly as possible. The only time-consuming part of this task is opening and subsequently closing a doll, so you want to minimize how often you do this. For example, the minimum number of openings (and subsequent closings) when combining group $[1, 2, 6]$ with the group $[4]$ is two, since you have to open the dolls with sizes $6$ and $4$. When combining group $[1, 2, 5]$ with the group $[3, 4]$, you need to perform three openings.

Write a program to calculate the minimum number of openings required to combine all disassembled matryoshka sets.

输入格式

The input consists of a single test case. A test case consists of two lines. The first line contains one integer $n (1 \leq n \leq 500)$ representing the number of individual dolls in the row. The second line contains $n$ positive integers specifying the sizes of the dolls in the order they appear in the row. Each size is between $1$ and $500$ inclusive.

输出格式

Display the minimum number of openings required when reassembling the matryoshka sets. If reassembling cannot be done (some of the kids might have been excessively zealous and taken some dolls), display the word Impossible.

题目大意

【题目描述】

套娃是俄罗斯传统木制玩具，由一组逐渐变小的娃娃组成，依次放置在另一个娃娃内部。一个套娃可以打开，露出一个更小的类似玩偶，而这个玩偶内部又有另一个玩偶，以此类推。

俄罗斯套娃博物馆最近展出了一系列设计相似的套娃，不同之处仅在于每套娃娃中嵌套的数量不同。不幸的是，一些过于热心（显然没有得到监督）的孩子把这些套娃拆散了，并将所有的单个娃娃排成一行。现在这一行中有 $n$ 个娃娃，每个都有一个整数大小。你需要重新组装这些套娃，既不知道套娃的数量，也不知道每套娃娃中娃娃的数量。你只知道每套完整的套娃由大小从 $1$ 到某个数字 $m$ 的连续大小的娃娃组成，而这个数字 $m$ 在不同的套娃中可能有所不同。

在重新组装套娃时，你必须遵循以下规则：

• 你只能将一个娃娃或一个嵌套的娃娃组放入一个更大的娃娃中。
• 你只能合并两个在行中相邻的娃娃组。
• 一旦一个娃娃成为一个组的成员，它不能被转移到另一个组或永久地从组中分离。它只能在合并两个组时暂时分离。

你的时间非常宝贵，你希望尽快完成这个重新组装过程。这个任务中唯一耗时的部分是打开和随后关闭一个娃娃，因此你希望尽量减少这样的操作次数。例如，当将组 $[1, 2, 6]$ 与组 $[4]$ 合并时，最少需要进行两次开关操作，因为你必须打开大小为 $6$ 和 $4$ 的娃娃。而当将组 $[1, 2, 5]$ 与组 $[3, 4]$ 合并时，需要进行三次开关操作。

编写一个程序计算重新组装所有拆散的套娃所需的最少开关次数。

【输入格式】

输入包含一个测试用例。测试用例由两行组成。第一行包含一个整数 $n (1 \leq n \leq 500)$，表示行中单个娃娃的数量。第二行包含 $n$ 个正整数，按照它们在行中出现的顺序指定娃娃的大小。每个大小在 $1$ 到 $500$ 之间（包括 $1$ 和 $500$）。

【输出格式】

输出重新组装套娃所需的最少开关次数。如果重新组装无法完成（可能有些孩子过于热心，带走了一些娃娃），则输出 Impossible。

翻译来自于：ChatGPT。

7
1 2 1 2 4 3 3

Impossible

7
1 2 3 2 4 1 3

7