盘子装运公司是一家网络零售商,顾名思义,是一家只销售盘子的公司。该公司销售的盘子由不计其数的生产厂商提供,品种是全宇宙最多的,为此公司的员工倍感自豪。
在最近的一次成本分析中,公司员工发现,他们花费了大量金钱在盘子的装箱环节。一部分原因是盘子在被运输工具运走前,需要被堆成一堆。很显然,这个阶段较预期浪费了大量的时间。或许你可以为公司提供帮助。
一次装运的盘子由若干厂商生产的盘子组合而成。各家厂商将其生产的盘子从小到大堆成一堆(小盘在上,大盘在下),再运送到公司。我们称上述按照顺序排列的盘堆顺序合理。为了方便装运,你必须将来自各个厂商的盘子重新组合成顺序合理的一堆。将来自各厂商的盘堆组合成一个盘堆时,可以进行如下两种操作:
拆分(Split):可以将一个盘堆堆顶任意数目的盘子抬起,并放置在原堆的一侧,使堆一分为二。
合并(Join):可以将一个盘堆放置在另一堆的堆顶,前提是在上方的堆最底层的盘子尺寸不大于在下方的堆最顶层的盘子尺寸。
注意不能将一个盘堆堆顶上的若干盘子直接移动到另一个盘堆的堆顶,必须先拆分,后合并。给定盘堆若干,你需要求出将这些盘堆通过两种操作合并成一堆的最少次数。下面的图是对输入输出样例的解释。