C. Денежные операции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Васином городе есть 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.

В третьем примере одним из оптимальных ответов является следующая последовательность действий:

  1. перечислить из первого банка во второй сумму 1;
  2. перечислить из второго банка в третий сумму 3;
  3. перечислить из третьего банка в четвертый сумму 6.