题目描述

Alicia 有一个数组 $a_1, a_2, \ldots, a_n$，其中每个元素都是非负整数。对于每个 $1 \leq i \leq n$，她计算了一个非负整数 $x_i = \max(0, a_1, \ldots, a_{i-1})$。注意，当 $i=1$ 时，$x_1 = 0$。

例如，如果 Alicia 的数组为 $a = \{0, 1, 2, 0, 3\}$，那么 $x = \{0, 0, 1, 2, 2\}$。

接着，她又计算了一个数组 $b_1, b_2, \ldots, b_n$，其中 $b_i = a_i - x_i$。

例如，如果 Alicia 的数组为 $a = \{0, 1, 2, 0, 3\}$，那么 $b = \{0-0, 1-0, 2-1, 0-2, 3-2\} = \{0, 1, 1, -2, 1\}$。

现在，Alicia 给出了 $b_1, b_2, \ldots, b_n$ 的值，要求你还原出 $a_1, a_2, \ldots, a_n$ 的值。你能帮她解决这个问题吗？

输入格式

第一行包含一个整数 $n$（$3 \leq n \leq 200\,000$），表示 Alicia 的数组的元素个数。

第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$-10^9 \leq b_i \leq 10^9$）。

保证对于给定的 $b$ 数组，存在一个解 $a_1, a_2, \ldots, a_n$，并且所有元素都满足 $0 \leq a_i \leq 10^9$。

输出格式

输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$），使得按照题目中的方法计算 $x$ 后，有 $b_1 = a_1 - x_1, b_2 = a_2 - x_2, \ldots, b_n = a_n - x_n$。

保证对于给定的测试数据至少存在一个解，并且解是唯一的。

说明/提示

第一个测试样例已在题目描述中给出。

第二个测试样例中，如果 Alicia 的数组为 $a = \{1000, 1000000000, 0\}$，那么 $x = \{0, 1000, 1000000000\}$，$b = \{1000-0, 1000000000-1000, 0-1000000000\} = \{1000, 999999000, -1000000000\}$。

由 ChatGPT 4.1 翻译

样例

5
0 1 1 -2 1

0 1 2 0 3 

3
1000 999999000 -1000000000

1000 1000000000 0 

5
2 1 2 2 3

2 3 5 7 10