407864: GYM102911 A Academic Recovery

Cindy's research project involves tracing the number of people infected by the Cordon Bleu virus, down to the minute. She has recorded the number of new cases for each of the first $$$N$$$ minutes. Specifically, she knows that $$$0$$$ people were infected at minute $$$0$$$, and she recorded that at the $$$i$$$th minute, $$$A_i$$$ more people were infected by the virus, for each $$$i$$$ from $$$1$$$ to $$$N$$$. It is guaranteed that the $$$A_i$$$ are non-negative integers.

Based on this, she constructed a second array $$$B$$$ of $$$N$$$ integers, the cumulative number of cases by the $$$i$$$th minute. That is, $$$B_i$$$ counts the total number of people infected on or before the $$$i$$$th minute.

Cindy keeps all her data in her laptop. Unfortunately, her laptop got infected by a (computer) virus and all the data in her hard drive got scrambled! Cindy also doesn't have any backups of her data, neither locally or on the cloud. How irresponsible! Always back up your data.

The original array $$$A$$$ was deleted. Cindy was able to recover the elements of $$$B$$$, but they were shuffled around randomly and ended up in the wrong order!

Given the elements of $$$B$$$ in some random order, help Cindy reconstruct the elements of the original array $$$A$$$, and give them in the correct order. It can be shown that $$$A$$$ can always be recovered, and furthermore that this answer is unique.

The first line of input contains a single integer $$$N$$$, the number of minutes that were tracked.

The second line of input contains $$$N$$$ space-separated integers, the elements of $$$B$$$ in some random order.

Output $$$N$$$ space-separated integers $$$A_1$$$, $$$A_2$$$, $$$\dots$$$, $$$A_N$$$ that are consistent with the values of $$$B$$$ given in the input.

$$$0 \le A_i \le 10^6$$$

Note that the constraint is given for $$$A$$$, not $$$B$$$.

Subtask 1 (50 points):

$$$1 \le N \le 5$$$

Subtask 2 (20 points):

$$$1 \le N \le 1000$$$

Subtask 3 (30 points):

$$$1 \le N \le 2\cdot 10^5$$$

5
3 1 4 1 5

1 0 2 1 1

We can show that if the values of $$$A$$$ are $$$\{1, 0, 2, 1, 1\}$$$, in that order, then we produce a cumulative array $$$B$$$ whose values can be rearranged to form $$$\{3, 1, 4, 1, 5\}$$$. We can show that this $$$A$$$ is unique.