The statement of this problem is similar to that of
problem P92795: “Balance (1)”.
But here, the *n* weights do not need to be 2^{0}, 2^{1}, …, 2^{n−1}.

I.e., the problem is:
Given *n* weights,
we have to place all the weights on a balance, one after another,
in such a way that the right pan is never heavier than the left pan.
Please compute the number of ways of doing this.

**Input**

Input consists of several cases,
each with the number of weights *n*
followed by *n* different weights, all between 1 and 10^{6}.
Assume 1 ≤ *n* ≤ 8.

**Output**

For every case, print the number of correct ways
of placing the weights on the balance.
This number will never be larger than 10^{7}.

Public test cases

**Input**

1 20 3 1 2 4 3 6 10 4 8 1 2 3 4 5 6 7 8

**Output**

1 15 17 2130717

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++ Java
- Event
- Novè Concurs de Programació de la UPC - Final
- Date
- 2011-09-21