#include <iostream>
#include <stack>
using namespace std;
 
void InsertInSortedOrder(stack<int>& s, int element) {
    if (s.empty() || s.top() <= element) {
        s.push(element);
        return;
    }
 
    int topElement = s.top();
    s.pop();
    InsertInSortedOrder(s, element);
    s.push(topElement);
}
 
void SortStack(stack<int>& s) {
    if (!s.empty()) {
        int topElement = s.top();
        s.pop();
        SortStack(s);
        InsertInSortedOrder(s, topElement);
    }
}
 
void PrintStack(stack<int> s) {
    if (s.empty()) {
        return;
    }
 
    int topElement = s.top();
    s.pop();
    cout << topElement << " ";
    PrintStack(s);
    s.push(topElement);
}
 
int main() {
    stack<int> s;
    s.push(30);
    s.push(-5);
    s.push(18);
    s.push(14);
    s.push(-3);
 
    cout << "Original Stack: ";
    PrintStack(s);
    cout << endl;
 
    SortStack(s);
 
    cout << "Sorted Stack: ";
    PrintStack(s);
    cout << endl;
 
    return 0;
}