import java.util.*;
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;
                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.left) {
                        node = p;
                        rotateRight(node);
                    }
                    rotateLeft(gf);
                    node.parent.color = 'B';
                    gf.color = 'R';
                }
            }
        }
        
        root.color = 'B'; 
    }

    
    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 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;
    }

    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());
        
        for (int i = 0; i < N; i++) {
            int t = Integer.parseInt(st.nextToken());
            Insert(t); 
        }

        preOrder(root);
    }
}