Hay $N$ monstruos parados en fila en un campo. La salud del $i$-ésimo monstruo es $h_i$.

Debes derrotar a todos los monstruos del campo. Para derrotar a un monstruo, debes reducir su salud a $0$ o menos.

Para derrotar a los monstruos, puedes elegir dos enteros $l \le r$ y lanzar un ataque de área a los monstruos desde el $l$-ésimo hasta el $r$-ésimo.

Los monstruos alcanzados por este ataque de área ven su salud reducida en $(N - r + l)!$.

Calcula el número mínimo de ataques de área que debes lanzar para derrotar a todos los monstruos.

$n!$ es el producto de todos los enteros desde $1$ hasta $n$.

Entrada

La primera línea contiene un entero $N$. $(1 \le N \le 500)$

La segunda línea contiene $h_1, h_2, \ldots, h_N$ separados por espacios. $(1 \le h_i \le 5000)$

Salida

La primera línea debe contener el número mínimo de ataques de área necesarios para derrotar a todos los monstruos.

Ejemplos

Entrada 1

4
1 2 3 4

Salida 1

2

Entrada 2

1
5000

Salida 2

5000