Il y a $N$ monstres alignés sur un terrain. La santé du $i$-ième monstre est $h_i$.

Vous devez éliminer tous les monstres du terrain. Pour éliminer un monstre, vous devez réduire sa santé à $0$ ou moins.

Pour éliminer les monstres, vous pouvez choisir deux entiers $l \le r$ et lancer une attaque de zone sur les monstres du $l$-ième au $r$-ième.

Les monstres touchés par cette attaque voient leur santé diminuer de $(N - r + l)!$.

Déterminez le nombre minimum d'attaques de zone nécessaires pour éliminer tous les monstres.

$n!$ est le produit de tous les entiers de $1$ à $n$.

Entrée

La première ligne contient un entier $N$. $(1 \le N \le 500)$

La deuxième ligne contient $h_1, h_2, \ldots, h_N$ séparés par des espaces. $(1 \le h_i \le 5000)$

Sortie

La première ligne contient le nombre minimum d'attaques de zone nécessaires pour éliminer tous les monstres.

Exemples

Entrée 1

4
1 2 3 4

Sortie 1

2

Entrée 2

1
5000

Sortie 2

5000