题解

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

typedef long long ll; // 避免累加溢出

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); // 加速输入输出，处理1e6数据必备

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
    cin >> a[i];
}

// 计算拼接数组的前缀和（长度2n，覆盖所有环形情况）
vector<ll> sum(2 * n);
sum[0] = 0;
for (int i = 1; i < 2 * n; ++i) {  // 仅需计算到2n-1（k+n-1最大为n+n-1=2n-1）
    sum[i] = sum[i - 1] + a[(i - 1) % n];
}

deque<int> dq;  // 单调队列：存储sum的下标，保证队列内sum值递增
int ans = 0;

// 遍历拼接数组的前缀和，维护长度为n的滑动窗口
for (int r = 1; r < 2 * n; ++r) {  // r为窗口右端点，范围1~2n-1
    // 1. 维护单调队列：移除队尾比sum[r]大的元素，保证队列递增
    while (!dq.empty() && sum[r] <= sum[dq.back()]) {
        dq.pop_back();
    }
    dq.push_back(r);

    // 2. 移除超出窗口的元素（窗口长度为n，左边界 = r - n + 1）
    int left = r - n + 1;
    while (!dq.empty() && dq.front() < left) {
        dq.pop_front();
    }

    // 3. 仅处理有效k（k=left，且k≤n）
    if (r >= n && left <= n) {  // r≥n时窗口长度才为n，left≤n限制k的有效范围
        // 窗口内sum的最小值 ≥ sum[k-1] → 所有前缀和≥0
        if (sum[dq.front()] >= sum[left - 1]) {
            ans++;
        }
    }
}

cout << ans << endl;
return 0;

}