#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 50 | 10 | 1s | 128MB | Minimum |

2 | 50 | 10 | 1s | 128MB | Minimum |

3 | 0 | 1 | 1s | 128MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o mathforjaneIII -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512