D. Башни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Город D состоит из n башен, установленных последовательно на одной прямой. Высота i-той по порядку башни (слева направо) в последовательности равна hi. Мэр города затеял перестройку, после которой город должен стать красивым. В красивом городе все башни расположены слева направо по неубыванию высот.

Перестройка состоит из выполнения нескольких (возможно нуля) операций. За одну операцию разрешается краном поднять любую башню и установить ее целиком на верх какой-то соседней башни. Другими словами, можно взять i-тую по порядку башню, и установить на верх либо (i - 1)-ой (если такая существует), либо (i + 1)-ой (если такая существует) по порядку башни. Высота получившейся башни равняется сумме высот соединенных башен. После этого две соединенные башни уже нельзя разъединить никаким образом, но с получившейся башней можно снова проводить подобные операции. Обратите внимание на то, что после выполнения одной операции общее количество башен, стоящих на прямой, уменьшается на 1.

Помогите мэру определить наименьшее количество операций, с помощью которых можно перестроить город в красивый.

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

Первая строка содержит единственное целое число n (1 ≤ n ≤ 5000) — количество башен в городе. Следующая строка содержит n целых чисел, разделенных пробелами: i-тое по порядку число hi (1 ≤ hi ≤ 105) обозначает высоту i-той по порядку башни (слева направо) в изначальной последовательности башен.

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

Выведите единственное целое число — наименьшее количество операций, которое требуется, чтобы перестроить город в красивый.

Примеры
Входные данные
5
8 2 7 3 1
Выходные данные
3
Входные данные
3
5 2 1
Выходные данные
2