HDU4193 Non-negative Partial Sums

// cin 会超时，不用 deque 会快一点
#include 
#include 
#include 
using namespace std;
const int MAXN = 2000010;
int a[MAXN];
int main()
{
    int n;
    while (scanf("%d", &n;))
    {
        if (n == 0) break;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a;[i]);
            a[i+n] = a[i];
        }
        for (int i = 1; i <= n*2; i++)
        {
            a[i] += a[i-1];
        }

        deque q;
        int ans = 0;
        for (int i = 1; i <= n*2; i++)
        {
            while (!q.empty() && a[q.back()]>=a[i]) q.pop_back();
            q.push_back(i);
            if (i > n && a[i - n] <= a[q.front()]) ++ans;
            if (!q.empty() && i - q.front() >= n - 1) q.pop_front();
        }
        printf("%d\n", ans);
    }
    return 0;
}