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?Input
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$.Output
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.Examplesinput
5 0 1 1 -2 1
output
0 1 2 0 3
input
3 1000 999999000 -1000000000
output
1000 1000000000 0
input
5 2 1 2 2 3
output
2 3 5 7 10
Note
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\}$.
Solution:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> b(n); for (int i = 0; i < n; i++) { cin >> b[i]; } vector<int> a(n); int x = 0; for (int i = 0; i < n; i++) { a[i] = b[i] + x; x = max(x, a[i]); } for (int i = 0; i < n; i++) { if (i > 0) cout << " "; cout << a[i]; } cout << '\n'; return 0; }