非负的部分和

【题目描述】

WZK最近收到了一个任务。

给出一个n个数的序列，为A0，A1，……，An-1，循环移动k位之后，这个序列就变成了Ak，Ak+1，……，An-1，A0，A1，……，Ak-1。一种优秀的循环移动是，对于任意的前i(1<=i<=n)项和都满足不小于零。请给出这个序列优秀循环移动的个数。

这道题目当然是很简单啦，但是WZK忙着吃小浣熊干脆面，手上油油的写不了程序，于是就麻烦你啦！如果能做到满分，他就会考虑请你吃一包哦~

【输入格式】

第一行一个整数n(1 <= n <= 10^6)，表示有n个数。

第二行n个整数，Ai(-1000 <= Ai <= 1000)表示给出的第i个数。

【输出格式】

一行一个整数，表示优秀循环移动的个数。

【样例输入】

3

2 2 1

【样例输出】

3

【提示】

【数据规模】

对于100%的数据有n<=10000。

对于100%的数据有n<=1000000。

【来源】

在此键入。