Codeforces Round 353 (Div. 2) |
---|
Закончено |
В Васином городе есть n банков, расположенных по кругу так, что соседними являются банки, номера которых различаются на 1, а также банк номер 1 и банк номер n (если n > 1). При этом, сам себе банк соседом не является.
В каждом банке у Васи есть счёт с каким-нибудь балансом. Заметим, что он может быть и отрицательным, если Вася должен банку.
Васе доступна следующая операция: взять два соседних банка и перечислить со счёта в одном банке на счёт в другом любое количество денег. При этом нет никаких ограничений на размер переводимой суммы или текущее состояние счёта в любом из банков.
Вася путается в больших числах, поэтому он просит вас определить, за какое минимальное количество операций он может обнулить сумму денег, лежащую на счёте в каждом из банков. Гарантируется, что Вася может это сделать, то есть суммарный баланс Васи по всем банкам равен нулю.
В первой строке входных данных записано единственное целое число n (1 ≤ n ≤ 100 000) — количество банков.
Во второй строке записаны n целых чисел ai ( - 109 ≤ ai ≤ 109), i-е из которых определяет баланс Васи в i-м банке. Гарантируется, что сумма всех ai равна 0.
Выведите минимальное количество операций, за которое Вася может обнулить баланс в каждом банке.
3
5 0 -5
1
4
-1 0 1 0
2
4
1 2 3 -6
3
В первом примере можно перечислить из первого банка в третий сумму 5.
Во втором примере можно перечислить сначала из третьего банка во второй, а потом из второго в первый сумму 1.
В третьем примере одним из оптимальных ответов является следующая последовательность действий:
Название |
---|