Tree Insertions

Time limit1sMemory limit128 MB

Summary

Count how many permutations of a given sequence build the same binary search tree; values may repeat and answers need big integers.

Level: Hard8 of 10
Topics: Tree, Combinatorics, Dynamic programming, Recursion
Solved: No attempts yet

Problem

All modern banks employ information systems to process their data. The amount of data is enormous - imagine all the transactions, payments, e-banking, web services, and so on. Advanced data structures are therefore needed to store the data and access it very quickly.

A Binary Search Tree (BST) is one example of such a data structure. It holds a collection of values together with a comparison operation that provides a linear ordering on those values.

A BST consists of nodes, each holding one value and having at most two child nodes: a left child and a right child (so a BST is a binary tree). The left subtree always contains only values strictly less than the node's value, and the right subtree only values greater than or equal to the node's value.

As a consequence, a value can be looked up easily by traversing the tree recursively. We start at the root, compare its value with the value we are searching for, and, depending on the result, descend into either the left or the right subtree - we never need to walk through both.

Inserting a value into an existing tree is just as simple. The first value (when the tree is empty) always becomes the root. If the tree already exists, we start at the root and traverse recursively, exactly as when searching. When the traversal reaches a missing child position, we create a new leaf node there and store the new value in it.

The figure below shows the tree after successively inserting the sequence 3, 4, 3, 5, 4, 1, 2.

Notice that different permutations of the same numbers often result in the same BST. For example, the tree in the fifth figure above can be built by three different input sequences:

3, 4, 3, 5, 4
3, 4, 5, 4, 3
3, 4, 5, 3, 4

Your task is to compute how many different permutations produce the same BST.

Input

The input consists of several trees, each specified on two lines. The first line contains a single integer $N$ ( $1 \le N \le 100$ ), the number of values in the tree. The second line contains $N$ values separated by spaces. Inserted in the given order, these values form the BST to be examined. All values are between $0$ and $1000$ inclusive.

The last tree is followed by a line containing a single zero.

Output

For each tree, output on its own line the total number of different permutations that would generate the same binary search tree. This number can exceed $2^{32}$ , so use arbitrary-precision (big-integer) arithmetic.

Examples1

Example 1

Input

5
3 4 3 5 4
7
3 4 3 5 4 1 2
31
16 8 24 4 12 20 28 2 6 10 14 18 22 26 30 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
0

Expected output

3
45
74836825861835980800000