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

class Main {
    static class Node {
        Node left, right, parent;
        int value, height;
        char color;
        public Node(int value) {
            this.value = value;
            this.height = 1;
            this.color = 'R';
        }
    }
    
    static Node Insert(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.value) {
            node.left = Insert(node.left, value);
            if (node.left != null) node.left.parent = node;
        } else if (value > node.value) {
            node.right = Insert(node.right, value);
            if (node.right != null) node.right.parent = node;
        }
        updateHeight(node);
        return reBalancing(node);
    }

    static void updateHeight(Node node) {
        if (node == null) return;
        int left_height = node.left == null ? 0 : node.left.height;
        int right_height = node.right == null ? 0 : node.right.height;
        node.height = Math.max(left_height, right_height) + 1;
    }

    static int getBalanceFactor(Node node) {
        if (node == null) return 0;
        int left_height = node.left == null? 0 : node.left.height;
        int right_height = node.right == null? 0 : node.right.height;
        return left_height - right_height;
    }

    static Node reBalancing(Node node) {
        while (node.parent != null && node.parent.color == 'R') {
            Node p = node.parent;
            Node gf = p.parent;

            if (p == gf.left) {
                Node u = gf.right;

                if (u != null && u.color == 'R') {
                    p.color = 'B';
                    u.color = 'B';
                    gf.color = 'R';
                    node = gf;
                } else {
                    if (node == p.right) {
                        node = p;
                        rotateLeft(node);
                    }
                    rotateRight(gf);
                    node.parent.color = 'B';
                    gf.color = 'R';
                }
            } else {
                Node u = gf.left;
                if ( u != null && u.color == 'R') {
                    p.color = 'B';
                    u.color = 'B';
                    gf.color = 'R';
                    node = gf;
                } else {
                    if (node == p.right) {
                        node = p;
                        rotateRight(node);
                    }
                    rotateLeft(gf);
                    node.parent.color = 'B';
                    gf.color = 'R';
                }
            }
            
        }
            
        return node;
    }

    static Node rotateLeft(Node node) {
        Node new_root = node.right;

        node.right = new_root.left;
        if (new_root.left != null) {
            new_root.left.parent = node;
        }

        new_root.parent = node.parent;
        if(new_root.parent != null) {
            if(new_root.parent.left == node) {
                new_root.parent.left = new_root;
            } else if (new_root.parent.right == node) {
                new_root.parent.right = new_root;
            }
        }

        new_root.left = node;
        node.parent = new_root;

        updateHeight(node);
        updateHeight(new_root);
        
        return new_root;
    }

    static Node rotateRight(Node node) {
        Node new_root = node.left;

        node.left = new_root.right;
        if(new_root.right != null) {
            new_root.right.parent = node;
        }

        new_root.parent = node.parent;
        if (new_root.parent != null) {
            if(new_root.parent.left == node) {
                new_root.parent.left = new_root;
            } else if (new_root.parent.right == node) {
                new_root.parent.right = new_root;
            }
        }

        new_root.right = node;
        node.parent = new_root;

        updateHeight(node);
        updateHeight(new_root);
        return new_root;
    }

    static Node Delete(Node node, int value) {
        if (node == null) return node;
        if (value < node.value) {
            node.left = Delete(node.left, value);
            if(node.left != null) node.left.parent = node;
        } else if (value > node.value) {
            node.right = Delete(node.right, value); 
            if(node.right != null) node.right.parent = node;
        } else {
            if (node.left == null) {
                Node temp = node.right;
                if (temp != null) temp.parent = node.parent;
                return temp;
                
            } else if (node.right == null) {
                Node temp = node.left;
                if (temp != null) temp.parent = node.parent;
                return temp;
            } else {
                Node minNode = node.right;
                while (minNode.left != null) {
                    minNode = minNode.left;
                }
                node.value = minNode.value;
                node.right = Delete(node.right, minNode.value);
                
            }
        }
        updateHeight(node);
        return reBalancing(node);
    }

    static void preOrder(Node node) {
        if (node == null) return;
        System.out.println(node.value+ " "+ node.color);
        preOrder(node.left);
        preOrder(node.right);
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        Node root = null;
        for (int i=0; i<N; i++) {
            int t = Integer.parseInt(st.nextToken());
            root = Insert(root, t);
            root.color = 'B';
        }

        preOrder(root);
    }
}