Problems "a" and "b" are similar, the only difference between them is that in problem "a" you can choose any two different indices when doing an operation, but in problem "b", you can only choose adjacent indices.
Zaid has an array $a$ of size $n$, Zaid thinks that for any two arrays $a$ and $b$, array $a$ is more beautiful than array $b$ if and only if array $a$ is lexicographically less than array $b$.
Zaid wants to make his array as beautiful as possible, and in order to do that he can do the following operation any number of times.
For example if we had the array $[$ $1$ , $5$ , $2$ , $3$ , $7$ $]$, and we have chosen $i = 4$ and $j = 2$, $a_4$ will become $a_4 + a_2$ which is $3 + 5 = 8$, then the element at index $2$ will be deleted, so the array will become $[$ $1$ , $2$ , $8$ , $7$ $]$.
Help Zaid and tell him the lexicographically minimum possible array he can get.
First line contains one integer $n$ $(1 \leq n \leq 3 \cdot 10^5)$ ,which is the length of the array.
The second line contains $n$ integers, the $i_{th}$ one is $a_i$ $(-10^9 \leq a_i \leq 10^9)$ ,which is the $i_{th}$ element in array $a$.
Print the elements of the lexicographically minimum possible array on a line separated by a space.
An array $x$ is lexicographically smaller than an array $y$ if there exists an index $i$ such that $x_i < y_i$, and $x_j = y_j$ for all $ 1 \le j < i$. Or if array $x$ is a prefix of array $y$ and $x \neq y$.
| Input | Output |
|---|---|
4 1 10 2 5 Copy
|
1 2 15 Copy
|
3 -1 -2 -3 Copy
|
-6 Copy
|
Hmm, the problem's name is "a", this gotta be a very simple and straightforward problem like it's name, right?
Like problem "b", if all values in the array are non-negative, then no operation is needed except for trailing zeroes.
Now if we have negative values, since we want to have the smallest first value, we should add all negative values together in the first index of a negative value, and add all the values before the first negative value to the last value in the array, then just go index by index, if we find two values where the left is larger than the right one, we add the left one to the end of the array.
There's a case where this solution won't work, if all the negative values form a suffix of the array, this way the last value of the array is the one that should have been the first, thus it won't work. To solve this case we either add all the negative values to the minimum non-negative value(except for the last one), or add all the negative values together except for the maximum one(except for the first negative value), in which we keep it as the last value of the array, or do the second option with the exception of the first option.