A. Сделай его возрастающим
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ положительных целых чисел, и массив $$$b$$$ размера $$$n$$$. Изначально $$$b_i=0$$$ для каждого $$$1 \leq i \leq n$$$.

За один ход вы можете выбрать целое число $$$i$$$ ($$$1 \leq i \leq n$$$) и прибавить $$$a_i$$$ к $$$b_i$$$ или вычесть $$$a_i$$$ из $$$b_i$$$. За какое минимальное число ходов можно сделать $$$b$$$ возрастающим (то есть таким, что каждый элемент строго больше всех предыдущих)?

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 5000$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива $$$a$$$.

Выходные данные

Выведите одно целое число — минимальное число ходов, за которое можно сделать $$$b$$$ возрастающим.

Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
4
Входные данные
7
1 2 1 2 1 2 1
Выходные данные
10
Входные данные
8
1 8 2 7 3 6 4 5
Выходные данные
16
Примечание

Пример $$$1$$$: можно вычесть $$$a_1$$$ из $$$b_1$$$, и прибавить $$$a_3$$$, $$$a_4$$$, $$$a_5$$$ к $$$b_3$$$, $$$b_4$$$ и $$$b_5$$$ соответственно. В итоге получим массив [$$$-1$$$, $$$0$$$, $$$3$$$, $$$4$$$, $$$5$$$] за $$$4$$$ хода.

Пример $$$2$$$: можно получить массив [$$$-3$$$, $$$-2$$$, $$$-1$$$, $$$0$$$, $$$1$$$, $$$2$$$, $$$3$$$] за $$$10$$$ ходов.