Город D состоит из n башен, установленных последовательно на одной прямой. Высота i-той по порядку башни (слева направо) в последовательности равна hi. Мэр города затеял перестройку, после которой город должен стать красивым. В красивом городе все башни расположены слева направо по неубыванию высот.
Перестройка состоит из выполнения нескольких (возможно нуля) операций. За одну операцию разрешается краном поднять любую башню и установить ее целиком на верх какой-то соседней башни. Другими словами, можно взять i-тую по порядку башню, и установить на верх либо (i - 1)-ой (если такая существует), либо (i + 1)-ой (если такая существует) по порядку башни. Высота получившейся башни равняется сумме высот соединенных башен. После этого две соединенные башни уже нельзя разъединить никаким образом, но с получившейся башней можно снова проводить подобные операции. Обратите внимание на то, что после выполнения одной операции общее количество башен, стоящих на прямой, уменьшается на 1.
Помогите мэру определить наименьшее количество операций, с помощью которых можно перестроить город в красивый.
Выходные данные
Выведите единственное целое число — наименьшее количество операций, которое требуется, чтобы перестроить город в красивый.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8 2 7 3 1
|
3
|
|
2
|
3
5 2 1
|
2
|