import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Node{
    int data;
    Node left,right;
    Node(int x) {
        data=x;
        left=right=null;
    }
}

class Main {
    public static Node createBinaryTree(int[] arr) {
        if (arr == null || arr.length == 0) return null;
    
        Node root = new Node(arr[0]);
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
    
        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            Node current = queue.poll();
    
            if (i < arr.length && arr[i] != -1) {
                current.left = new Node(arr[i]);
                queue.add(current.left);
            }
            i++;
    
            if (i < arr.length && arr[i] != -1) {
                current.right = new Node(arr[i]);
                queue.add(current.right);
            }
            i++;
        }
    
        return root;
    }

    public static void leftView(Node root){
        Queue<Node> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int n=q.size();
            for(int i=1;i<=n;i++){
                Node curr=q.poll();
                if(i==1)
                    System.out.print(curr.data+" ");
                if(curr.left!=null){
                    q.add(curr.left);
                }
                if(curr.right!=null){
                    q.add(curr.right);
                }
            }
        }
    }
    
    public static void rightView(Node root){
        Queue<Node> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int n=q.size();
            for(int i=1;i<=n;i++){
                Node curr=q.poll();
                if(i==n)
                    System.out.print(curr.data+" ");
                if(curr.left!=null){
                    q.add(curr.left);
                }
                if(curr.right!=null){
                    q.add(curr.right);
                }
            }
        }
    }

    public static void topView(Node root){
        if (root == null) return ;

        class Pair {
            Node node;
            int hd;

            Pair(Node node, int hd) {
                this.node = node;
                this.hd = hd;
            }
        }

        Map<Integer,Integer> mp = new TreeMap<>();
        Queue<Pair> q=new LinkedList<>();
        q.add(new Pair(root,0));
        while(!q.isEmpty()){
            Pair curr=q.poll();
            Node node=curr.node;
            int hd=curr.hd;
            
            if(!mp.containsKey(hd)){
                mp.put(hd,node.data);
            }

            if(node.left!=null){
                q.add(new Pair(node.left,hd-1));
            }
            if(node.right!=null){
                q.add(new Pair(node.right,hd+1));
            }
        }
        for (int data : mp.values()) {
            System.out.print(data+" ");
        }
    }

    
    public static void bottomView(Node root){
        if (root == null) return ;

        class Pair {
            Node node;
            int hd;

            Pair(Node node, int hd) {
                this.node = node;
                this.hd = hd;
            }
        }

        Map<Integer,Integer> mp = new TreeMap<>();
        Queue<Pair> q=new LinkedList<>();
        q.add(new Pair(root,0));
        while(!q.isEmpty()){
            Pair curr=q.poll();
            Node node=curr.node;
            int hd=curr.hd;
            
            mp.put(hd,node.data);

            if(node.left!=null){
                q.add(new Pair(node.left,hd-1));
            }
            if(node.right!=null){
                q.add(new Pair(node.right,hd+1));
            }
        }
        for (int data : mp.values()) {
            System.out.print(data+" ");
        }
    }
    public static void verticalOrderView(Node root){
        if (root == null) return ;

        class Pair {
            Node node;
            int hd;

            Pair(Node node, int hd) {
                this.node = node;
                this.hd = hd;
            }
        }

        Map<Integer,List<Integer>> mp = new TreeMap<>();
        Queue<Pair> q=new LinkedList<>();
        q.add(new Pair(root,0));
        while(!q.isEmpty()){
            Pair curr=q.poll();
            Node node=curr.node;
            int hd=curr.hd;
            
            if (!mp.containsKey(hd)) {
                mp.put(hd, new ArrayList<>());
            }
            mp.get(hd).add(node.data);

            if(node.left!=null){
                q.add(new Pair(node.left,hd-1));
            }
            if(node.right!=null){
                q.add(new Pair(node.right,hd+1));
            }
        }
        for (List<Integer> data : mp.values()) {
            System.out.print(data+" ");
        }
    }

    public static void printLeftBoundary(Node root, List<Integer> result){
        if(root==null || (root.left==null && root.right==null))
            return;
        
        result.add(root.data);

        if (root.left != null)
            printLeftBoundary(root.left, result);
        else
            printLeftBoundary(root.right, result);
    }
    
    public static void printLeaves(Node root, List<Integer> result){
        if(root==null)
            return;
        
        printLeaves(root.left, result);
        if (root.left == null && root.right == null)
            result.add(root.data);
        printLeaves(root.right, result);
    }
    
    public static void printRightBoundary(Node root, List<Integer> result){
        if(root==null || (root.left==null && root.right==null))
            return;
        
        if (root.right!= null)
            printRightBoundary(root.right, result);
        else
            printRightBoundary(root.left, result);
        
        result.add(root.data);
    }
    
    public static void boundaryOrder(Node root){
        if(root==null) return;
        List<Integer> result=new ArrayList<>();
        result.add(root.data);
        
        printLeftBoundary(root.left, result);
        printLeaves(root, result);
        printRightBoundary(root.right, result);

        for(int i:result)
            System.out.print(i+" ");
    }
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int arr[]=new int[n];
        for(int i=0;i<n;i++)
            arr[i]=sc.nextInt();

        Node root=createBinaryTree(arr);
        leftView(root);
        System.out.println();
        rightView(root);
        System.out.println();
        topView(root);
        System.out.println();
        bottomView(root);
        System.out.println();
        verticalOrderView(root);
        System.out.println();
        boundaryOrder(root);
    }
}