Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Lauriel sống ở thành phố kì lạ, có n ngân hàng trong thành phố và chúng nằm hình tròn xung quanh nhà của cô. Các ngân hàng được đánh chỉ số từ 1 đến n. Hai ngân hàng được coi là lân cận nếu chỉ số của chúng khác nhau không quá 1 (ví dụ ngân hàng 2 lân cận ngân hàng 1 và 3). Ngoài ra ngân hàng 1 và ngân hàng n được coi là lân cận nhau nếu n > 1. Một ngân hàng không lân cận chính nó.

Lauriel có tài khoản tại mỗi ngân hàng. Tài khoản của cô có thể có số dư âm tức là cô đang nợ ngân hàng này một số tiền.

Chỉ có một hình thức giao dịch: chuyển một số tiền từ ngân hàng bất kì sang ngân hàng lân cận nó. Không có hạn chế về số tiền có thể chuyển và không mất phí khi thực hiện giao dịch.

Lauriel ghét phải làm thứ gì đó quá nhiều lần, nên cô muốn tìm số lần giao dịch tối thiểu để làm cho số dư trong tất cả tài khoản ở các ngân hàng của cô về 0. Chú ý rằng tổng số tiền trong tất cả ngân hàng của Lauriel bằng 0.

Input

Input description...

Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 100 000) – số ngân hàng ở thành phố của Lauriel.

Dòng thứ hai chứa n số nguyên a_i (-10⁹ ≤ a_i ≤ 10⁹), số nguyên thứ i là số dư ban đầu của tài khoản trong ngân hàng thứ i. Input đảm bảo tổng của tất cả a_i là bằng 0.

Output

Số lần giao dịch tối thiểu để đưa số dư trong tất cả tài khoản ở các ngân hàng của Lauriel về 0.

Example

Test 1
Input:
3
7 0 -7
Output:
1

Test 2
Input:
4
1 3 4 -8
Output:
3

Giải thích:
- Giải thích test 1 : Chuyển 7 từ ngân hàng thứ nhất sang thứ ba.
- Giải thích test 2 :
1. Chuyển 1 từ ngân hàng thứ nhất sang thứ hai.
2. Chuyển 4 từ ngân hàng thứ hai sang thứ ba.
3. Chuyển 8 từ ngân hàng thứ ba sang thứ tư.