농부 존의 소 \(N\)마리가 원을 이루어 서 있다. \(i\)번째 소는 정수 용량이 \(a_i\)리터인 양동이를 가지고 있다. 처음에는 모든 양동이가 가득 차 있다.

매분 \(1\le i<N\)인 소 \(i\)는 자신의 양동이에 든 우유를 모두 소 \(i+1\)에게 넘기고, 소 \(N\)은 자신의 우유를 소 \(1\)에게 넘긴다. 모든 교환은 동시에 일어난다. 예를 들어 어떤 소가 가득 찬 양동이에서 우유 \(x\)리터를 내보내는 동시에 \(x\)리터를 받으면, 그 소가 가진 우유의 양은 그대로 유지된다. 어떤 소가 가진 우유의 양이 양동이의 용량 \(a_i\)를 초과하면 넘친 우유는 사라진다.

\(1,2,\ldots,N\)분이 지난 각각의 시점에 모든 소에게 남아 있는 우유의 총량을 구하여라.

입력

첫째 줄에 정수 \(N\)이 주어진다. (\(1\le N\le 5\cdot 10^5\))

둘째 줄에 \(N\)개의 정수 \(a_1,a_2,\ldots,a_N\)이 주어진다. (\(1\le a_i\le 10^9\))

출력

\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)분이 지난 뒤 모든 소에게 남아 있는 우유의 총량을 출력한다.

예제 입력 1

6
2 2 2 1 2 1

예제 출력 1

8
7
6
6
6
6

처음 각 양동이에 든 우유의 양은 \([2,2,2,1,2,1]\)이다.

• \(1\)분 뒤에는 \([1,2,2,1,1,1]\)이므로 우유의 총량은 \(8\)이다.
• \(2\)분 뒤에는 \([1,1,2,1,1,1]\)이므로 우유의 총량은 \(7\)이다.
• \(3\)분 뒤에는 \([1,1,1,1,1,1]\)이므로 우유의 총량은 \(6\)이다.
• \(4\)분 뒤에는 \([1,1,1,1,1,1]\)이므로 우유의 총량은 \(6\)이다.
• \(5\)분 뒤에는 \([1,1,1,1,1,1]\)이므로 우유의 총량은 \(6\)이다.
• \(6\)분 뒤에는 \([1,1,1,1,1,1]\)이므로 우유의 총량은 \(6\)이다.

예제 입력 2

8
3 8 6 4 8 3 8 1

예제 출력 2

25
20
17
14
12
10
8
8

\(1\)분 뒤 각 양동이에 든 우유의 양은 \([1,3,6,4,4,3,3,1]\)이므로 우유의 총량은 \(25\)이다.

예제 입력 3

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

예제 출력 3

2000000053
1000000054
56
49
42
35
28
24
20
20

서브태스크

출처

USACO 2024 February Contest, Gold, Problem 2. Milk Exchange