There are $N$ monsters standing in a row on a field. The health of the $i$-th monster is $h_i$.

You must defeat all the monsters on the field. To defeat a monster, you must reduce its health to $0$ or less.

To defeat the monsters, you can choose two integers $l \le r$ and cast an area-of-effect attack on the monsters from the $l$-th to the $r$-th position.

Monsters hit by this area-of-effect attack have their health reduced by $(N - r + l)!$.

Find the minimum number of area-of-effect attacks required to defeat all monsters.

$n!$ is the product of all integers from $1$ to $n$.

Input

The first line contains an integer $N$. $(1 \le N \le 500)$

The second line contains $h_1, h_2, \ldots, h_N$ separated by spaces. $(1 \le h_i \le 5000)$

Output

The first line outputs the minimum number of area-of-effect attacks required to defeat all monsters.

Examples

Input 1

4
1 2 3 4

Output 1

2

Input 2

1
5000

Output 2

5000