You are given a stack of integers st, write a program to sort it. You can use another stack if needed.

Problem Note

  • The top of the stack must point to the smallest element.
  • The stack must be sorted in increasing order from the top of the stack to its bottom.

Example 1

Input: Top -> [4,3,1,6,2,5]
Output: Top -> [1,2,3,4,5,6]
Explanation: All the elements of the given stack are sorted with minimum element at the top of the stack.

Example 2

Input: Top -> [1,2,3]
Output: Top -> [1,2,3]
Explanation: All the elements of the given stack are sorted with minimum element at the top of the stack.

Example 3

Input: Top -> [10,9,3,1]
Output: Top -> [1,3,9,10]
Explanation: All the elements of the given stack are sorted with minimum element at the top of the stack.