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 = 5$, $a_4$ will become $a_4 + a_5$ which is $3 + 7 = 10$, then the element at index $5$ will be deleted, so the array will become $[$ $1$ , $5$ , $2$ , $10$ $]$.
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 |
|---|---|
3 10 -3 20 Copy
|
7 20 Copy
|
2 1 0 Copy
|
1 Copy
|
4 -1 5 -1 -1 Copy
|
-1 3 Copy
|
If all elements are non-negative then it's optimal to not do any operations, because adding two non-negative integers will not decrease any value. But trailing zeros are an exception, it's always better to remove them.
If there is a negative element at index $i$ then it's always better to do the operation on index $i-1$, since it will always decrease it.
So the solution is to do the operation as long as there's a negative value in the array, and to also handle trailing zeros in the end.
To write a fast solution you can use a stack; add element by element of the array to the top of the stack, and while doing so whenever the top of the stack is negative, pop the top of the stack and do the operation(add the popped value to the top of the stack).