Magry的强迫症

题目描述

Magry的老豆因为工作的原因经常出差去海拉尔，回家的时候经常会带来来自俄罗斯的东西（毕竟那边靠近中俄边境，卖俄罗斯的东西特别多），比如套娃……以至于Magry的家里有好多好多的套娃。

现在Magry把家里的n个套娃排成一行，你的任务是把它们套成若干个套娃组，使得每个套娃组内的套娃编号恰好是从1开始的连续编号（套娃编号和它的大小是有关联的，编号越小套娃越小，1号套娃是最小的）。

然而Magry有强迫症，他需要你只能按照如下规则进行组套娃操作：

1. 套娃只能将小的套进大的里面，大小相等的套娃相互不能套；
2. 每次只能把相邻的两个套娃组合合并成一个套娃组；
3. 一旦有两个套娃属于同一个组，它们永远都属于同一个组（只有与相邻组合并的过程中会临时拆散）。

执行合并操作的前后，所有套娃都是关闭的。为了合并两个套娃组，你需要交替地把一些套娃打开、重新套起来、关闭。例如：为了合并[1,2,6]和[4]，需要打开套娃6和4；为了合并[1,2,5]和[3,4]，需要打开套娃5,4,3（只有先打开4才能打开3）。

Magry的强迫症还要求打开套娃的总次数最少，并且还要求把小的套娃组放进去后马上关闭套娃。

那么问题来了：打开套娃操作总次数是多少次才能满足Magry的强迫症？

输入

多组测试数据，以EOF结尾。

每组数据分为两行。

第一行为一个数n，表示套娃个数。$1 \leq n \leq 200$

第二行，每行n个整数a，表示Magry桌上摆的各个套娃的大小标号。$1 \leq a \leq 200$

输出

对于每组数据，输出一行。

若有解，则输出最少操作次数。

若无解，输出There is no way to meet Magry's requirements.

输入样例

4
1 2 4 3
4
2 3 1 2

输出样例

4
There is no way to meet Magry's requirements.

样例解释

对于样例一最少步骤4步的完成步骤如下：

设所求最小操作次数为cnt，初值为0.

1. 组装1,2，需要打开套娃2，将1放进2中，关闭2，成为[1,2]，此时cnt+=1；
2. 组装[1,2]和4，需要打开套娃4，将[1,2]放进4中，关闭4，成为[1,2,4]，此时cnt+=1；
3. 组装[1,2,4]和3，需要打开套娃4，3，将[1,2]放进3中，关闭3，再将[1,2,3]放进4中，关闭4，成为[1,2,3,4]，此时cnt+=2。

最后结果cnt=4。

Source

UVa 1579