← 返回题目列表

Codeforces · 675/C

C. 汇款

中文机器翻译题面 查看原题

Vasya 居住的城市中有 n 家银行,它们位于一个圆圈中,如果它们的索引相差不超过 1,则任何两家银行都是相邻的。此外,如果 n > 1,则银行 1 和银行 n 是相邻的。没有银行是其自身的邻居。

Vasya 在每家银行都有一个账户。它的余额可能是负数,这意味着 Vasya 欠这家银行一些钱。

只有一种类型的操作可用:将一定金额的资金从任何银行转入任何邻近银行的账户。对于执行此操作的转账金额或余额要求没有限制。

Vasya 不喜欢处理大数字,因此他要求你确定将每个银行帐户的余额更改为零所需的最少操作次数。可以保证的是,这是可以实现的,即Vasya在所有银行的总余额为零。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 存储体数量。

第二行包含n个整数ai (- 109 ≤ ai ≤ 109),其中第i个等于第i家银行账户的初始余额。保证所有ai的总和等于0。

输出

打印将每个银行的余额更改为零所需的最少操作数。

示例

输入 #1

3
5 0 -5

输出 #1

1

输入 #2

4
-1 0 1 0

输出 #2

2

输入 #3

4
1 2 3 -6

输出 #3

3

注意

在第一个示例中,Vasya 可能会将 5 从第一​​个银行转移到第三个银行。

在第二个示例中,Vasya 可能首先将 1 从第三个存储体传输到第二个存储体,然后将 1 从第二个存储体传输到第一个存储体。

在第三个示例中,以下序列提供了最佳答案:

1.从第一银行转1到第二银行;
2.从第二家银行转账3到第三家;
3.将6从第三银行转至第四银行。