Maximums

题意翻译

对于一个序列 $\{a_n\}$，定义序列 $\{c_n\}$ ：$c_i=\max\{0,a_1,\cdots,a_{i-1}\}$ 。同时定义序列 $\{b_n\} :b_i=a_i-c_i$ 。 给定 $\{b_n\}$ ，求 $\{a_n\}$ 。 $1\leq n\leq 200,000$

题目描述

Alicia has an array, $ a_1, a_2, \ldots, a_n $ , of non-negative integers. For each $ 1 \leq i \leq n $ , she has found a non-negative integer $ x_i = max(0, a_1, \ldots, a_{i-1}) $ . Note that for $ i=1 $ , $ x_i = 0 $ . For example, if Alicia had the array $ a = \{0, 1, 2, 0, 3\} $ , then $ x = \{0, 0, 1, 2, 2\} $ . Then, she calculated an array, $ b_1, b_2, \ldots, b_n $ : $ b_i = a_i - x_i $ . For example, if Alicia had the array $ a = \{0, 1, 2, 0, 3\} $ , $ b = \{0-0, 1-0, 2-1, 0-2, 3-2\} = \{0, 1, 1, -2, 1\} $ . Alicia gives you the values $ b_1, b_2, \ldots, b_n $ and asks you to restore the values $ a_1, a_2, \ldots, a_n $ . Can you help her solve the problem?

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 3 \leq n \leq 200\,000 $ ) – the number of elements in Alicia's array. The next line contains $ n $ integers, $ b_1, b_2, \ldots, b_n $ ( $ -10^9 \leq b_i \leq 10^9 $ ). It is guaranteed that for the given array $ b $ there is a solution $ a_1, a_2, \ldots, a_n $ , for all elements of which the following is true: $ 0 \leq a_i \leq 10^9 $ .

输出格式

Print $ n $ integers, $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ), such that if you calculate $ x $ according to the statement, $ b_1 $ will be equal to $ a_1 - x_1 $ , $ b_2 $ will be equal to $ a_2 - x_2 $ , ..., and $ b_n $ will be equal to $ a_n - x_n $ . It is guaranteed that there exists at least one solution for the given tests. It can be shown that the solution is unique.

输入输出样例

输入样例 #1

5
0 1 1 -2 1

输出样例 #1

0 1 2 0 3

输入样例 #2

3
1000 999999000 -1000000000

输出样例 #2

1000 1000000000 0

输入样例 #3

5
2 1 2 2 3

输出样例 #3

2 3 5 7 10

说明

The first test was described in the problem statement. In the second test, if Alicia had an array $ a = \{1000, 1000000000, 0\} $ , then $ x = \{0, 1000, 1000000000\} $ and $ b = \{1000-0, 1000000000-1000, 0-1000000000\} = \{1000, 999999000, -1000000000\} $ .