Balance

Time limit2sMemory limit128 MB

Summary

Count the orders and pan choices for placing n distinct weights so the left pan is never heavier than the right at any step.

Level: Medium4 of 10
Topics: Brute force, Backtracking, Recursion, Combinatorics
Solved: No attempts yet

Problem

We are given a two-pan balance and $n$ weights of distinct masses $a_1, a_2, \ldots, a_n$ . We must place the weights on the balance one at a time so that at no moment is the left pan heavier than the right pan. At each step, we pick one weight that has not yet been placed and put it on either the left pan or the right pan. We repeat this until all weights have been used. Write a program that computes the number of ways to do this.

Input

The first line contains the integer $n$ ( $0 < n < 10$ ). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $0 < a_1, a_2, \ldots, a_n < 1000$ ).

Output

Output a single integer: the number of ways.

Examples1

Example 1
Input
```
3
1 2 4
```
Expected output
```
15
```