如果一个长度为 $m$ 的不同数字序列 $a_1, \dots, a_m$ 不存在满足 $1 \le i < j < k \le m$ 且 $a_k < a_i < a_j$ 的三元组 $(i, j, k)$，则称该序列为“无 231 序列”。

Bobo 有一个 $1, \dots, n$ 的排列 $p_1, \dots, p_n$，他可以从中删除一些元素（可以不删除，但不能全部删除）。请计算在所有 $(2^n - 1)$ 种可能的剩余序列中，有多少个是无 231 序列。

输入格式

输入包含多组测试数据，以文件结束符（EOF）结束。对于每组测试数据： 第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $p_1, \dots, p_n$。

• $1 \le n \le 50$
• 对于每个 $1 \le i \le n$，$1 \le p_i \le n$
• 在每组输入中，$n$ 的总和不超过 $500$。

输出格式

对于每组测试数据，输出一个整数，表示无 231 序列的数量。

样例

输入格式 1

2
2 1

输出格式 1

3

输入格式 2

3
1 2 3

输出格式 2

7

输入格式 3

4
2 3 4 1

输出格式 3

11