{"problem":{"name":"[USACO24FEB] Milk Exchange G","description":{"content":"Farmer John 的 $N$（$1\\le N \\le 5\\cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\\le a_i\\le 10^9$）升的桶。所有桶初始时都是满的。 每一分钟，对于 $1\\le i<N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10194"},"statements":[{"statement_type":"Markdown","content":"Farmer John 的 $N$（$1\\le N \\le 5\\cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\\le a_i\\le 10^9$）升的桶。所有桶初始时都是满的。\n\n每一分钟，对于 $1\\le i<N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满的，送出 $x$ 升牛奶同时收到 $x$ 升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。\n\n在 $1,2,\\ldots,N$ 的每一分钟后，所有奶牛总共还余下多少牛奶？ \n\n## Input\n\n输入的第一行包含 $N$。\n\n第二行包含 $a_1,a_2,\\ldots,a_N$。\n\n## Output\n\n输出 $N$ 行，其中第 $i$ 行包含 $i$ 分钟后所有奶牛总共余下的牛奶量。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n最初，每个桶中的牛奶量为 $[2,2,2,1,2,1]$。\n\n- $1$ 分钟后，每个桶中的牛奶量为 $[1,2,2,1,1,1]$，因此总牛奶量为 $8$。\n- $2$ 分钟后，每个桶中的牛奶量为 $[1,1,2,1,1,1]$，因此总牛奶量为 $7$。\n- $3$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。\n- $4$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。\n- $5$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。\n- $6$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。\n\n### 样例解释 2\n\n$1$ 分钟后，每个桶中的牛奶量为 $[1,3,6,4,4,3,3,1]$，因此总牛奶量为 $25$。\n\n### 测试点性质\n\n- 测试点 $4-5$：$N\\le 2000$。\n- 测试点 $6-8$：$a_i\\le 2$。\n- 测试点 $9-13$：所有 $a_i$ 在范围 $[1,10^9]$ 内均匀随机生成。\n- 测试点 $14-23$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10194","tags":["USACO","2024","O2优化","前缀和","差分","单调栈"],"sample_group":[["6\n2 2 2 1 2 1","8\n7\n6\n6\n6\n6"],["8\n3 8 6 4 8 3 8 1","25\n20\n17\n14\n12\n10\n8\n8"],["10\n9 9 10 10 6 8 2 1000000000 1000000000 1000000000","2000000053\n1000000054\n56\n49\n42\n35\n28\n24\n20\n20"]],"created_at":"2026-03-03 11:09:25"}}