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 #cf_span(class=[tex-font-style-underline], body=[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 <= A_i <= 10^6$
*Note that the constraint is given for $A$, not $B$.*
*Subtask 1* (50 points):
$1 <= N <= 5$
*Subtask 2* (20 points):
$1 <= N <= 1000$
*Subtask 3* (30 points):
$1 <= N <= 2 dot.op 10^5$
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.
## Input
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
Output $N$ space-separated integers $A_1$, $A_2$, $\\dots$, $A_N$ that are consistent with the values of $B$ given in the input.
[samples]
## Scoring
$0 <= A_i <= 10^6$*Note that the constraint is given for $A$, not $B$.**Subtask 1* (50 points): $1 <= N <= 5$ *Subtask 2* (20 points): $1 <= N <= 1000$*Subtask 3* (30 points): $1 <= N <= 2 dot.op 10^5$
## Note
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.
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of minutes.
Let $ B = \{b_1, b_2, \dots, b_N\} $ be a multiset of integers representing the shuffled cumulative counts, where $ b_i = \sum_{j=1}^i A_j $ for some unique sequence $ A = (A_1, A_2, \dots, A_N) $ with $ A_i \in \mathbb{Z}_{\geq 0} $.
Let $ B_{\text{sorted}} = (b_{(1)}, b_{(2)}, \dots, b_{(N)}) $ be the sorted version of $ B $ in increasing order, with $ b_{(1)} \leq b_{(2)} \leq \dots \leq b_{(N)} $.
**Constraints**
1. $ 1 \leq N \leq 2 \cdot 10^5 $
2. $ 0 \leq A_i \leq 10^6 $ for all $ i \in \{1, \dots, N\} $
3. $ B_1 = A_1 $, $ B_i = B_{i-1} + A_i $ for $ i \geq 2 $, and $ B_N = \sum_{j=1}^N A_j $
4. The multiset $ \{B_1, B_2, \dots, B_N\} $ is given in arbitrary order.
**Objective**
Reconstruct the unique sequence $ A = (A_1, A_2, \dots, A_N) $ such that:
$$
A_i = b_{(i)} - b_{(i-1)} \quad \text{for } i = 1, \dots, N
$$
where $ b_{(0)} = 0 $, and $ b_{(i)} $ is the $ i $-th smallest element of the given multiset $ B $.