На поле в ряд стоят $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