161. Sort a Stack

Challenge1000 ms256 MBSolved by 0%

Read n values pushed onto a stack in the order given, sort the stack so the largest value ends up on top, then print the stack from TOP to bottom.

So pushing 3 1 4 2 and sorting gives 4 3 2 1 when printed from the top.

Solve it using only stack operations and one temporary stack — no arrays, no sorting library. That constraint is the exercise.

Constraints - `1 ≤ n ≤ 2000` - `-1000000 ≤ value ≤ 1000000`

Input

The first line contains an integer n. The second line contains n space-separated integers, pushed onto the stack in that order — so the LAST value given ends up on top.

Output

Print the sorted stack from TOP to bottom on one line, separated by single spaces — largest first.

Input4 3 1 4 2

Output4 3 2 1

Noteis the worked example from the statement

Input1 7

Output7

Noteis a single value, where the sorting loop does nothing

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution