using System;

public class Program

{

    public static void Main()

    {

        BST bst = new BST();

        int numberOfNodes,cnt = 0,val;

        numberOfNodes = int.Parse(Console.ReadLine());

        while(cnt < numberOfNodes)

        {

            val = int.Parse(Console.ReadLine());

            bst.Insert(val);

            cnt++;

        }

        bst.PrintAscending();

        Console.WriteLine();

        bst.PrintDescending();

    }

​

}

​

public class Node

{

    public int data;

    public Node right;

    public Node left;

    public Node parent;

    public int flag;

    public Node(int data)

    {

        this.data = data;

        this.right = null;

        this.left = null;

        this.parent = null;

        this.flag = 0;

    }

}

​

public class BST

{

    Node root;

    public BST()

    {

        this.root = null;

    }

    public void Insert(int val)

    {

        Node curr = root;

        Node node = new Node(val);

        if(root == null)

        {

            root = node;

            curr = node;

        }

        else

        {

            while(true)

            {

                if(node.data > curr.data)

                {

                    if(curr.right == null)

                        break;

                    else

                        curr = curr.right;

                }

                else

                {

                    if(curr.left == null)

                    {

                        break;

                    }

                    else

                    {

                        curr = curr.left;   

                    }

                }

            }

            if(node.data > curr.data)

            {

                node.parent = curr;

                curr.right = node;

            }

            else

            {

                node.parent = curr;

                curr.left = node;

            }

        }

​

    }

​

    public void PrintAscending()

    {

        Node curr = root;

        int c = 0;

        int flagZero = 0, flagOne = 1;

        if(root.flag == 1)

        {

            flagZero = 1;

            flagOne = 0;

        }

        while(c < 3)

        {

            if(curr == root)

            {

                c++;

            }

            if(curr == null)

                break;

            if(curr.left == null || curr.left.flag == flagOne)

            {

                if(curr.flag == flagZero )

                {

                    Console.Write(curr.data+" ");

                    curr.flag = flagOne;

                }

                if(curr.right != null && curr.right.flag == flagZero)

                {

                    curr = curr.right;

                }

                else

                {

                    curr = curr.parent;

                }

            }

            else

            {

                curr = curr.left;

            }

        }

    }

public void PrintDescending()

    {

        Node curr = root;

        int c = 0;

        int flagZero = 0, flagOne = 1;

        if(root.flag == 1)

        {

            flagZero = 1;

            flagOne = 0;

        }

        while(c < 3)

        {

            if(curr == root)

            {

                c++;

            }

            if(curr == null)

                break;

            if(curr.right == null || curr.right.flag == flagOne)

            {

                if(curr.flag == flagZero )

                {

                    Console.Write(curr.data+" ");

                    curr.flag = flagOne;

                }

                if(curr.left != null && curr.left.flag == flagZero)

                {

                    curr = curr.left;

                }

                else

                {

                    curr = curr.parent;

                }

            }

​

            else

            {

                curr = curr.right;

            }

        }

    }

}

​