問題文

中身の見えない袋に $N$ 個のボールが入っています．全てのボールには一つの整数が書かれていて，$i$ 個目のボール（$1 \le i \le N$）に書かれている整数は $A_i$ です．

あなたは袋から $N$ 個のボールを一個ずつ取り出すゲームに挑戦します．このとき，取り出したボールに書かれている整数が単調非減少（すなわち，$t$ 個目に取り出したボール $(1 \le t \le N)$ に書かれた整数を $B_t$ として，$B_t \le B_{t + 1}$ が $t = 1, \dots, N - 1$ 全てで成立）であればあなたの勝利です．逆に，ゲームのいずれかの時点で直前に取り出したボールより小さい番号のボールを取り出してしまった場合，あなたは全てのボールを袋に戻して中身をよく混ぜ，再度はじめからこのゲームに挑戦します．なお，ボールの形状は均一で，袋からボールを取り出す際に各ボールが選ばれる確率は全て等しいです．

あなたがこのゲームに一度勝利するまでに必要な挑戦回数の期待値を求めてください．答えは $4 \times 10^{18}$ 未満の整数になることが本問題の制約から証明できます．

入力

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

• $2 \le N \le 20$
• $1 \le A_i \le N \, (1 \le i \le N)$
• 入力は全て整数

出力

答えとなる整数を出力してください．最後に改行してください．

サンプル

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