Minimal Direction Changes Route

Farmer Nhoj dropped Bessie in the middle of nowhere! At time \(t=0\), Bessie is located at \(x=0\) on an infinite number line. Every second she moves exactly \(1\) unit either to the left or to the right. She searches frantically for an exit, but there is none; after \(T\) seconds she ends up back at \(x=0\) — tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times she crosses the boundaries \(x=0.5, 1.5, 2.5, \ldots, (N-1).5\). These counts are given by an array \(A_0, A_1, \ldots, A_{N-1}\) with \(1 \le N \le 10^5\), \(1 \le A_i \le 10^6\) and \(\sum A_i \le 10^6\). It is guaranteed that Bessie never reaches \(x N\).

Bessie’s route can be represented by a string of \(T = \sum_{i=0}^{N-1}A_i\) characters, each being either L or R, where the i-th character describes the direction she moves during the i-th second. The number of direction changes is defined as the number of occurrences of LR plus the number of occurrences of RL in the route.

Your task is to help Farmer Nhoj produce any valid route that is consistent with the given array \(A\) and minimizes the number of direction changes. It is guaranteed that at least one valid route exists.

Hint: One way to interpret the information is to observe that each boundary between \(x=i\) and \(x=i+1\) is crossed exactly \(A_i\) times. Since Bessie starts and ends at \(x=0\) and never goes below 0 or above \(N\), for every boundary the number of crossings in each direction must be equal. Hence, if we let \(m_i = A_i/2\) (which is an integer by validity), then any valid route must cross the boundary between \(i\) and \(i+1\) exactly \(2m_i\) times. Moreover, the sequence \(m_0, m_1, \ldots, m_{N-1}\) is nonincreasing. A natural construction is to view the route as a sequence of nested excursions. For each excursion \(j\) from \(1\) to \(m_0\), let \(k\) be the largest index such that \(m_k \ge j\). Then a mountain excursion from \(x=0\) to \(x=k+1\) and back written as \(R^{k+1}L^{k+1}\) will contribute exactly 2 crossings to each boundary from \(x=i\) to \(x=i+1\) for all \(0 \le i \le k\). Concatenating these excursions (for \(j=1\) to \(m_0\)) yields a valid route. Although consecutive excursions will add an extra reversal between them, it turns out that this construction minimizes the total number of direction changes.

inputFormat

The first line contains a single integer \(N\). The second line contains \(N\) space-separated integers \(A_0, A_1, \ldots, A_{N-1}\).

It is guaranteed that \(1 \le N \le 10^5\), \(1 \le A_i \le 10^6\), \(\sum A_i \le 10^6\), and that there exists at least one valid route.

outputFormat

Output a single line containing a string of length \(T = \sum_{i=0}^{N-1}A_i\) consisting of the characters L and R — a valid route with the minimum number of direction changes.

sample

1
2

RL