Reverse a Stack Using Recursion

You are given a stack of integers. Your task is to reverse the stack using recursion without using any extra space other than the internal stack space used due to recursion. You are not allowed to use any loop constructs (e.g., for, while, etc.). Only the following inbuilt stack methods are permitted:

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.

Input:

The first line of input contains an integer value N, denoting the size of the input Stack.
The second line contains N single space-separated integers, denoting the stack elements, where the last (Nth) element is the TOP most element of Stack.

Output:

N single space-separated integers in a single line, where the first integer denotes the TOP element of the reversed stack.

Example:

Input:

3
2 1 3

Output:

2 1 3

Explanation:

First-line contains an integer 3; this is the size of the stack. The second-line contains the elements of the stack. After reversing, the stack elements in a single line are printed, starting from the top element: 2 1 3.

Constraints:

• 0 <= N <= 10^3
• Time Limit: 1 sec