Hôm nay cũng như mọi ngày, Hưng cảm thấy quá chán vì những cuộc đối đầu thông thường cùng Nhân Thiện và Vương Lượng nên anh quyết định sẽ trôn 2 người này bằng 1 thử thách mới. Thử thách như sau: Hưng triệu hồi lên một vòng tròn gồm \(N\) số rồi cho Nhân và Lượng chọn vị trí bất kì để có thể đi hết được vòng tròn. Điều kiện để đi được hết vòng tròn như sau: Gọi \(i\) là vị trí mà Vương Lượng và Nhân đang đứng. Nếu :

• \(a[i]>0\)

• \(a[i]+a[i+1]>0\)

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

• …

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

• …

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

thì \(i\) là vị trí mà Nhân và Lượng có thể chọn để đi hết vòng tròn. Mỗi lần đi được hết vòng tròn Nhân và Lượng sẽ được 1 điểm. Đúng lúc này Mr.Toàn lại rủ cả nhóm đi uống bia mà Hưng lại đang thách đố hai bạn nên chỉ khi Nhân và Lượng đạt được số điểm tối đa và thoát ra khỏi vòng tròn cả bọn mới có thể đi được. Các bạn hãy giúp tìm số điểm tối đa nhé !!!

Dữ liệu

• Dòng đầu tiên là số nguyên dương \(N(N \leq 10^6\))

• Dòng tiếp theo gồm \(N\) số nguyên \(( |a[i]| \leq 10^9\))

Input

5
0 1 -2 10 3

Output

2