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

class Main {
    static class Node {
        Node left, right, parent;
        int value;
        char color;
        public Node(int value) {
            this.value = value;
            this.color = 'R';
        }
    }

    
    static Node root = null; 

    static void Insert(int value) {
        Node newNode = new Node(value);
        if (root == null) {
            root = newNode;
            root.color = 'B';
            return;
        }

        Node current = root;
        Node parent = null;
        
        
        while (current != null) {
            parent = current;
            if (value < current.value) {
                current = current.left;
            } else if (value > current.value) {
                current = current.right;
            } else {
                return;
            }
        }

        newNode.parent = parent;
        if (value < parent.value) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        reBalancing(newNode);
    }

    static void 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;
                // case 1
                if (u != null && u.color == 'R') {
                    p.color = 'B';
                    u.color = 'B'; 
                    gf.color = 'R';
                    node = gf;
                } else { // case 3
                    if (node == p.right) {
                        rotateLeft(p);
                        rotateRight(gf);

                        node.color = 'B';
                        p.color = 'R';
                        gf.color = 'R';
                    } else {
                        //case 2
                        rotateRight(gf);
                        p.color = 'B';
                        node.color = 'R';
                        gf.color = 'R';
                    }
                    break;
                }
            }
            else {
                Node u = gf.left;
                // case 1 
                if (u != null && u.color == 'R') {
                    p.color = 'B';
                    u.color = 'B';
                    gf.color = 'R';
                    node = gf;
                } else {
                    if (node == p.left) {
                        rotateRight(p);
                        rotateLeft(gf);
                        p.color = 'B';
                        node.color = 'R';
                        gf.color = 'R';
                    } else {
                        rotateLeft(gf);
                        p.color = 'B';
                        node.color = 'R';
                        gf.color = 'R';
                    }
                    break;
                }
            }
        }
        if (root != null) {
            root.color = 'B'; // 근데 루트가 null일 경우가 있을 수 있나? 
        }
    }

    static void 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 (node.parent == null) {
            root= new_root;
        } else if (node == node.parent.left) {
            node.parent.left = new_root;
        } else {
            node.parent.right = new_root; 
        }

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

    static void preOrder(Node node) {
        if (node == null) return;
        System.out.println(node.value + " " + node.color);
        preOrder(node.left);
        preOrder(node.right);
    }

    static void 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 (node.parent == null) {
            root = new_root;
        } else if (node == node.parent.left) {
            node.parent.left = new_root; 
        } else {
            node.parent.right = new_root;
        }
        new_root.right = node;
        node.parent = new_root;
    }
    
    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());
        for (int i = 0; i < N; i++) {
            int t = Integer.parseInt(st.nextToken());
            Insert(t); 
        }
        preOrder(root);
    }
}