場上有 $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