Treasure Tree Command Sequence

Little X found a peculiar repeating machine that can send commands to a robot. The robot stands initially at the root of an infinite complete binary tree. There is a connected subtree (the "treasure tree") hidden inside the complete binary tree. This subtree contains exactly n nodes, it always includes the root, and every node in this subtree hides a treasure.

You are given the preorder traversal of the treasure tree. The treasure tree is a subtree of the infinite complete binary tree. In the infinite complete binary tree, every node has a left child and a right child. In the treasure tree, if a node’s child is missing then that branch is not part of the connected block. In other words, for every node in the treasure tree (other than the root) its parent is also in the tree. Moreover, if a node appears in the preorder list then its children in the treasure tree can be determined by checking whether 2*v (for the left child) and 2*v+1 (for the right child) belong to the set of treasure nodes.

The repeating machine will replay the command string you input infinitely. Each command is one of the following characters:

• L: move the robot from its current node to the left child;
• R: move the robot from its current node to the right child;
• U: move the robot from its current node to its parent (if at the root, this command is illegal).

When the robot visits a node containing treasure (it may visit nodes repeatedly) the treasure is mined.

Your task is to find a shortest command string (consisting only of the letters L, R, U) such that when the robot executes this command string repeatedly (infinitely), it eventually visits every treasure node.

Hint: The treasure tree is a connected subtree of the complete binary tree, and its structure can be reconstructed using the following observation: a node v in the treasure tree has a left child if and only if 2*v is present in the preorder list, and a right child if and only if 2*v+1 is present. A solution is to perform an Euler tour (a DFS that returns to the root) on the treasure tree; the moves recorded along the way form a valid command string. Note that if the tree has only the root, the answer is an empty string.

inputFormat

The input consists of two lines. The first line contains a positive integer n (n ≥ 1), the number of nodes in the treasure tree. The second line contains n space‐separated distinct positive integers representing the nodes of the treasure tree in a preorder traversal. It is guaranteed that the treasure tree is a connected subtree of the infinite complete binary tree (the root is always 1) and that for every node v (except 1) in the tree, its parent (i.e. ⌊v/2⌋) is also in the tree.

outputFormat

Output a shortest command string (a string composed solely of the characters L, R, U) such that when the robot executes the string repeatedly (infinitely), it will visit every treasure node at least once. If the treasure tree consists of only one node (the root), output an empty string.

sample

1
1