import java.util.*;
class Node{
    int data;
    Node left;
    Node right;
    Node(int data){
        this.data=data;
        this.left=null;
        this.right=null;
    }
}
class Tree{
    Node root;
        Tree(){
            root=null;
        }
        void insert(int data){
            if(root==null){
                root =new Node(data);
            }else
            _insert(root,data);
        }
        void _insert(Node current,int data){
            if(data<current.data){
                if(current.left==null)
                current.left=new Node(data);
                else
                _insert(current.left,data);
            }else{
                if(current.right==null)
                current.right=new Node(data);
                else
                _insert(current.right,data);
                
            }
        }
    void pre(Node node){
        if(node==null) return;
        System.out.print(node.data+" ");
        pre(node.left);
        pre(node.right);
    }
    void in(Node node){
        if(node==null) return;
        in(node.left);
        System.out.print(node.data+" ");
        in(node.right);
    }
    void post(Node node){
        if(node==null) return;
        post(node.left);
        post(node.right);
        System.out.print(node.data+" ");
    }
}
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        Tree tree=new Tree();
        if(n<0){
            System.out.println("Invalid input");
            return;
        }
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            int s=sc.nextInt();
            tree.insert(s);
        }
        tree.pre(tree.root);
        System.out.println();
        tree.in(tree.root);
        System.out.println();
        tree.post(tree.root);
    }
}