Đi uống bia

ĐỀ BÀI: ĐI UỐNG BIA

Hưng tạo ra một vòng tròn gồm \(N\) số nguyên \(a[1], a[2], \dots, a[N]\). Nhân và Lượng cần chọn một vị trí xuất phát \(i\) (\(1 \le i \le N\)) bất kỳ để đi hết một vòng tròn theo chiều kim đồng hồ.

Vị trí \(i\) được coi là hợp lệ (đi hết được vòng tròn) nếu tất cả các tổng tiền tố từ vị trí \(i\) đều nhận giá trị dương (\(> 0\)), cụ thể:

• \(a[i] > 0\)
• \(a[i] + a[i+1] > 0\)
• \(a[i] + a[i+1] + a[i+2] > 0\)
• \(\dots\)
• \(a[i] + a[i+1] + \dots + a[n] + a[1] + \dots + a[i-1] > 0\)

Yêu cầu: Đếm số lượng vị trí xuất phát \(i\) hợp lệ.

Dữ liệu vào:

• Dòng 1: Chứa số nguyên dương \(N\) (\(1 \le N \le 10^6\)).
• Dòng 2: Chứa \(N\) số nguyên \(a[1], a[2], \dots, a[N]\) (\(\vert{}a[i]\vert{} \le 10^9\)).

Dữ liệu ra:

• In ra một số nguyên duy nhất là số vị trí xuất phát hợp lệ.

Ví dụ:

Input

5
0 1 -2 10 3

Output

2

Giải thích:

• Vị trí xuất phát \(i = 4\) (giá trị \(10\)): các tổng lần lượt là \(10\), \(10+3=13\), \(13+0=13\), \(13+1=14\), \(14+(-2)=12 > 0\) (Hợp lệ).
• Vị trí xuất phát \(i = 5\) (giá trị \(3\)): các tổng lần lượt là \(3\), \(3+0=3\), \(3+1=4\), \(4+(-2)=2\), \(2+10=12 > 0\) (Hợp lệ).
• Tổng cộng có \(2\) vị trí hợp lệ.