Milk Exchange
Farmer John's N (1≤N≤5⋅105) cows are lined up in a circle. The ith cow has a bucket with integer capacity ai (1≤ai≤109) liters. All buckets are initially full.
Every minute, cow i will pass all the milk in their bucket to cow i+1 for 1≤i<N, with cow N passing its milk to cow 1. All exchanges happen simultaneously (i.e., if a cow has a full bucket but gives away x liters of milk and also receives x liters, her milk is preserved). If a cow's total milk ever ends up exceeding ai, then the excess milk will be lost.
After each of 1,2,…,N minutes, how much total milk is left among all cows?
Initially, the amount of milk in each bucket is [2,2,2,1,2,1].
- After 1 minute, the amount of milk in each bucket is [1,2,2,1,1,1] so the total amount of milk is 8.
- After 2 minutes, the amount of milk in each bucket is [1,1,2,1,1,1] so the total amount of milk is 7.
- After 3 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.
- After 4 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.
- After 5 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.
- After 6 minutes, the amount of milk in each bucket is [1,1,1,1,1,1] so the total amount of milk is 6.
After 1 minute, the amount of milk in each bucket is [1,3,6,4,4,3,3,1] so the total amount of milk is 25.
SCORING:
- Inputs 4-5: N≤2000
- Inputs 6-8: ai≤2
- Inputs 9-13: All ai are generated uniformly at random in the range [1,109].
- Inputs 14-23: No additional constraints.
Problem credits: Chongtian Ma, Alex Liang, Patrick Deng
Source: USA Computing Olympiad.
Input Format
The first line contains N.
The next line contains integers a1,a2,...,aN.
Output Format
Output N lines, where the i-th line is the total milk left among all cows after i minutes.