Na polu w rzędzie stoi $N$ potworów. $i$-ty potwór ma $h_i$ punktów życia.

Musisz pokonać wszystkie potwory na polu. Aby pokonać potwora, musisz sprawić, by jego punkty życia spadły do $0$ lub mniej.

Aby pokonać potwory, możesz wybrać dwie liczby całkowite $l \le r$ i wykonać atak obszarowy na potwory od $l$-tego do $r$-tego.

Potwory trafione tym atakiem tracą $(N - r + l)!$ punktów życia.

Oblicz minimalną liczbę ataków obszarowych potrzebną do pokonania wszystkich potworów.

$n!$ to iloczyn wszystkich liczb całkowitych od $1$ do $n$.

Wejście

W pierwszej linii podano liczbę całkowitą $N$. $(1 \le N \le 500)$

W drugiej linii podano $h_1, h_2, \ldots, h_N$ oddzielone spacjami. $(1 \le h_i \le 5000)$

Wyjście

W pierwszej linii wypisz minimalną liczbę ataków obszarowych potrzebną do pokonania wszystkich potworów.

Przykład

Wejście 1

4
1 2 3 4

Wyjście 1

2

Wejście 2

1
5000

Wyjście 2

5000