1787: STEMA-P-4 “双塔积木堆放”

有 n 块长度不同的积木从左到右排成一排，现需要将所有积木按照以下要求堆放在 A、B 位置，A、B 位置初始没有积木。 

堆放要求： 

1）从左到右依次拿取积木堆放在 A 位置或 B 位置的顶部，且堆放后不能再改变该积木位置； 

2）堆放过程中，如果该位置没有积木，那么可以直接堆放拿取的积木；

如果该位置有积木，只有拿取的积木长度小于该位置顶部的积木时，才可以堆放。 

提示：所有积木堆放完后 A 位置或 B 位置可以没有积木。 

例如：

n = 2；从左到右 2 块积木的长度依次为 2、1，如下图所示： 

按要求，从左到右先堆放长度为 2 的积木，再堆放长度为 1 的积木，有如下 4 种不同的堆放方法： 

第一种：先将长度为 2 的积木堆放在 A 位置，因为 1 小于 2，再将长度为 1 的积木堆放在 A 位置顶部； 

第二种：先将长度为 2 的积木堆放在 A 位置，再将长度为 1 的积木堆放在 B 位置； 

第三种：先将长度为 2 的积木堆放在 B 位置，再将长度为 1 的积木堆放在 A 位置； 

第四种：先将长度为 2 的积木堆放在 B 位置，因为 1 小于 2，再将长度为 1 的积木堆放在 B 位置顶部。 

给定一个整数 n，以及从左到右 n 块积木的长度，请计算堆放完所有积木，一共有多少种不同的堆放方法；

如果按要求没有一种方法能堆放完所有积木，则输出 0。

第一行输入一个整数 n（1≤n≤20），表示积木数量； 

第二行输入 n 个不同的整数（1≤整数≤30），分别表示从左到右每块积木的长度，整数之间以一个空格隔开。

2
2 1

4