We are given a two-pan balance and n weights of different masses a₁, a₂, …, a_n. We are to put each one of the given weights on the balance, one after another, in such a way that at any moment the left pan is never heavier than the right pan. At each step, we choose one weight that is not yet placed on the balance, and we place it either on the left pan or on the right pan. We continue these steps, until we use all the weights. Write program balance, which calculates the number of ways to do this.

입력 형식

The integer n is given on the first row of the standard input (0 < n < 10). There are n integers on the second row: a₁, a₂, …, a_n (0 < a₁, a₂, …, a_n < 1000).

출력 형식

Your program have to output a single integer on the standard output – the searched number of ways.

예제 입력

3
1 2 4

예제 출력

15