フィールドに $N$ 匹のモンスターが一列に並んでいる。 $i$ 番目のモンスターの体力は $h_i$ である。

あなたはフィールドのすべてのモンスターを倒さなければならない。 モンスターを倒すためには、そのモンスターの体力を $0$ 以下にする必要がある。

モンスターを倒すために、あなたは二つの整数 $l \le r$ を選び、$l$ 番目から $r$ 番目までのモンスターに対して範囲攻撃を仕掛けることができる。

この範囲攻撃を受けたモンスターは、体力が $(N - r + l)!$ だけ減少する。

すべてのモンスターを倒すために必要な範囲攻撃の最小回数を求めよ。

$n!$ は $1$ から $n$ までのすべての整数の積である。

入力

最初の行に整数 $N$ が与えられる。 $(1 \le N \le 500)$

二番目の行に $h_1, h_2, \ldots, h_N$ が空白区切りで与えられる。 $(1 \le h_i \le 5000)$

出力

最初の行に、すべてのモンスターを倒すために必要な範囲攻撃の最小回数を出力する。

入出力例

入力 1

4
1 2 3 4

出力 1

2

入力 2

1
5000

出力 2

5000