俄罗斯套娃 Matryoshka

题目描述 Matryoshkas 指一套传统的，尺寸从小到大套在一起的俄罗斯木娃娃。 一套 Matryoshka 娃娃可以被打开，以便观察其内部一个确定的较小排列。这个排列内部又有更小的一种排列，如此继续下去。 俄罗斯套娃博物馆最近展出了一些类似设计的俄罗斯套娃，它们的唯一不同只是每组套娃内含娃娃的数量。 不幸的是，一些“热心”的（并且显然没有大人监督的）孩子把这些套在一起的娃娃分开，把所有的单个的套娃放在了一排。在这一排中有n个娃娃，每个都有一个整数的大小。你需要在不知道原来的套娃的数量和排列方式的情况下，重新组装这些娃娃。你只知道，每一个完整的套娃由大小为从1～m的连续整数的娃娃组成，m的大小在不同的套娃中可能是不同的。 当你重组娃娃的时候，你必须遵守以下规则： 你只能把套娃（或者单个的娃娃）放在更大的娃娃里 你只能组合相邻的娃娃 一旦一个娃娃被套进一组套娃里，它就不能被转移到另一组套娃里或者被长久地分开。仅仅当两组套娃被合并时，它才可以与一组套娃短暂地分离。 你的时间非常值钱，你也想尽可能快地完成合并的操作。这个任务唯一消耗时间的部分是拆开一个娃娃。所以你想尽可能最小化这个操作的次数。 例如，当合并套娃[1 、2、6] 和 [4]时，这个操作的次数是2，因为你要打开大小为6的和4的；合并[1、2、5]和[3、4]时，这个操作次数是3. 请编写一个程序来计算完成任务所需的最小操作次数。 输入 多组数据，每组数据两行. 第一行有一个整数n,为单行套娃的数量(1<=n<=500); 第二行有n个用空格整数分割的整数,表示每个套娃的尺寸，保证尺寸在1～500之间。 输出 对于每组数据，如果能成功合并，输出合并的最小操作次数； 如果无法合并（因为那些热心的孩子可能拿走了几个娃娃），输出“impossible”（不含引号）

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4371 [PDF](https://uva.onlinejudge.org/external/15/p1579.pdf)