Problem Description
Still remember those baby flash cards from the previous three weeks?
Card 1: Card 2: Card 3: Card 4: Card 5:
------- ------- ------- ------- -------
| | | * | |* * | |* *| |* * *|
| * | | | | *| |* * | | * * |
| | | * | |* * | | * * | |* * *|
------- ------- ------- ------- -------
Card 1 is actually number 1, Card 2 is number 2, Card 3 is number 5, Card 4 is number 6, Card 5 is number 8.
This week, Steven now wants to teach Jane some zig-zag patterns with these flash cards.
First, he picks N flash cards with unique numbers on it (N is an odd integer).
Then, he arranges the number in such a way that if Jane looks at the numbers (the flash cards) from left to right, the pattern is like this: / \ / ... \, or increasing-decreasing-increasing-...-decreasing.
How many different number arrangements of length N with such pattern that Steven can show to Jane this time?
Two number arrangements of length N are considered different if there is at least a pair of numbers that are exchanged.
Input
Each test case starts with one odd integer, N (3 <= N <= 9), that denotes the number of flash cards bought by Grace.
Then immediately followed by N positive integers less than 10000 that denote the number of dots on each flash card.
These N flash cards are always unique as described in the problem description above.
Input ends with a dummy test case with N = 0. Ignore this one.
Output
For each test case, print an integer in one line to answer Steven's NEW question above.
Sample Input
5 1 2 5 6 8
Sample Output
16
Problem Author
Steven Halim
This is an original and Steven will likely teach this to his baby daughter Jane sometime soon.
This problem is from CS3233 2012 Contest 3, Problem A. Modified to remove multiple testcases.