You are given a stack of integers, write a program to sort it. You could 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]

Example 2

Input: Top -> [1,2,3]
Output: Top -> [1,2,3]

Example 3

Input: Top -> [10,9,3,1]
Output: Top -> [1,3,9,10]