Stack Sorting

You are given a stack of integers. Your task is to sort the stack in descending order (i.e. the top of the stack will hold the highest element).

You are required to implement an algorithm that uses only stack operations. The idea is to use an auxiliary stack to help with the sorting. The algorithm should repeatedly pop elements from the input stack and push them into the temporary stack in a manner such that the temporary stack is always sorted in descending order. If the current element is greater than the top of the temporary stack, move elements back from the temporary stack into the input stack before pushing the current element.

For example, if the input stack is [3, 5, 1, 4, 2] (with the rightmost element being the top), the resulting sorted stack should be [5, 4, 3, 2, 1].

Note: All formulas or mathematical expressions should be rendered in LaTeX format. For example, if you need to show descending order, you can refer to it as \(a_1 \geq a_2 \geq \dots \geq a_n\).

inputFormat

The input is provided via stdin and has the following format:

• The first line contains a single integer \(n\), which represents the number of elements in the stack.
• The second line contains \(n\) space-separated integers representing the elements of the stack. The last integer in the line represents the top of the stack.

outputFormat

Output the sorted stack via stdout as a single line of \(n\) space-separated integers in descending order. The first integer in the output represents the bottom of the stack and the last integer represents the top.

5
3 5 1 4 2

5 4 3 2 1