Problem Statement

A bag whose contents cannot be seen contains $N$ balls. Each ball has one integer written on it, and the integer written on the $i$-th ball ($1 \le i \le N$) is $A_i$.

You take on a game in which you draw the $N$ balls from the bag one at a time. You win if the integers written on the drawn balls are monotonically non-decreasing (that is, letting $B_t$ be the integer written on the ball drawn $t$-th $(1 \le t \le N)$, $B_t \le B_{t + 1}$ holds for all $t = 1, \dots, N - 1$). Conversely, if at any point in the game you draw a ball with a smaller number than the ball drawn immediately before it, you return all the balls to the bag, mix the contents well, and attempt the game again from the beginning. The balls are uniform in shape, and when a ball is drawn from the bag, every ball is equally likely to be chosen.

Find the expected number of attempts needed until you win this game once. It can be proved from the constraints of this problem that the answer is an integer less than $4 \times 10^{18}$.

Input

$N$
$A_1\ A_2\ \dots \ A_N$

• $2 \le N \le 20$
• $1 \le A_i \le N \, (1 \le i \le N)$
• All inputs are integers.

Output

Output the integer that is the answer, followed by a newline.

Sample

2
2 1

2

5
5 2 2 2 2

5

20
10 9 8 7 6 5 4 3 1 2 12 11 13 14 16 15 18 17 20 19

2432902008176640000