#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100
int stact[MAX];
int top=-1;
int n;
void push(int x){
    if(top==n-1){
        return;
    }
    stack[++top]=x;
}
void sortStack(){
    int tempStack[MAX];
    int tempTop=-1;
    while(top!=-1){
        int temp=stack[top--];
        while (tempTop!=-1 && tempStack[tempTop]>temp){
            stack[++top]=tempStack[tempTop--];
        }
        tempStack[++tempTop]=temp;
    }
    while(tempTop!=-1){
        stack[++top]=tempStack[tempTop--];
    }
    for (int i=0;i<=top;i++){
        printf("%d",stack[i]);
        if (i<top) printf(" ");
    }
    printf("\n");
}
int main(){
    scanf("%d",&n);
    char command[10];
    int x;
    while(scanf("%s",command)!=EOF){
        if(strcmp(command,"push")==0){
            scanf("%d",&x);
            push(x);
        }else if(strcmp(command,"sort")==0){
            sortStack();
        }
    }
    return 0;
}