Balance (2) P17598


Statement
 

pdf   zip

html

The statement of this problem is similar to that of problem P92795: “Balance (1)”. But here, the n weights do not need to be 20, 21, …, 2n−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 106. 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 107.

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