CF675C.Money Transfers

There are n banks in the city where Vasya lives, they are located in a circle, such that any two banks are neighbouring if their indices differ by no more than 1. Also, bank 1 and bank n are neighbours if n > 1. No bank is a neighbour of itself.

Vasya has an account in each bank. Its balance may be negative, meaning Vasya owes some money to this bank.

There is only one type of operations available: transfer some amount of money from any bank to account in any neighbouring bank. There are no restrictions on the size of the sum being transferred or balance requirements to perform this operation.

Vasya doesn't like to deal with large numbers, so he asks you to determine the minimum number of operations required to change the balance of each bank account to zero. It's guaranteed, that this is possible to achieve, that is, the total balance of Vasya in all banks is equal to zero.

城市中有 $n$ 家银行，瓦夏住在该城市。这些银行呈环形排列，即：若两家银行的编号之差的绝对值不超过 $1$，则它们互为邻行；此外，当 $n > 1$ 时，编号为 $1$ 和编号为 $n$ 的银行也互为邻行。任意银行均不与自身相邻。

瓦夏在每家银行都开设了一个账户，其账户余额可能为负数（表示瓦夏欠该银行钱）。

仅允许一种操作：将任意数额的钱从某家银行的账户转账至其任意一个邻行的账户。对转账金额的大小以及执行该操作时各账户的余额均无任何限制。

瓦夏不喜欢处理大数字，因此他请你计算：使每家银行账户余额均变为零所需的最少操作次数。题目保证该目标一定可以实现，即瓦夏在所有银行的账户余额总和为零。

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of banks.

The second line contains n integers a__i ( - 109 ≤ a__i ≤ 109), the i-th of them is equal to the initial balance of the account in the i-th bank. It's guaranteed that the sum of all a__i is equal to 0.

输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 100\,000$）—— 银行的数量。

第二行包含 $n$ 个整数 $a_i$（$-10^9 ≤ a_i ≤ 10^9$），其中第 $i$ 个数表示第 $i$ 家银行账户的初始余额。保证所有 $a_i$ 的总和为 0。

Print the minimum number of operations required to change balance in each bank to zero.

输出将每家银行的余额变为零所需的最少操作次数。

In the first sample, Vasya may transfer 5 from the first bank to the third.

In the second sample, Vasya may first transfer 1 from the third bank to the second, and then 1 from the second to the first.

In the third sample, the following sequence provides the optimal answer:

1. transfer 1 from the first bank to the second bank;
2. transfer 3 from the second bank to the third;
3. transfer 6 from the third bank to the fourth.

在第一个样例中，Vasya 可以将 5 从第一家银行转移到第三家银行。

在第二个样例中，Vasya 可以先将 1 从第三家银行转移到第二家银行，再将 1 从第二家银行转移到第一家银行。

在第三个样例中，以下操作序列可得到最优解：

1. 将 1 从第一家银行转移到第二家银行；
2. 将 3 从第二家银行转移到第三家银行；
3. 将 6 从第三家银行转移到第四家银行。