Farmer Nhoj dropped Bessie in the middle of nowhere! At time $t=0$, Bessie is located at $x=0$ on an infinite number line. She frantically searches for an exit by moving left or right by $1$ unit each second. However, there actually is no exit and after $T$ seconds, Bessie is back at $x=0$, tired and resigned.
Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=.5,1.5,2.5,…,(N−1).5$, given by an array $A_0,A_1,…,A_{N−1} (1≤N≤10^5, 1≤A_i≤10^6, ∑A_i≤10^6)$. Bessie never reaches $x\gt N$ nor $x\lt 0$.
In particular, Bessie's route can be represented by a string of $T=∑_{i=0}^{N-1}A_i$ $L$s and $R$s where the $i$th character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of $LR$s plus the number of occurrences of $RL$s.
Please help Farmer Nhoj find any route Bessie could have taken that is consistent with $A$ and minimizes the number of direction changes. It is guaranteed that there is at least one valid route.
The first line contains $N$. The second line contains $A_0,A_1,…,A_{N−1}$.
Output a string $S$ of length $T=∑_{i=0}^{N−1}A_i$ where $S_i$ is $L$ or $R$, indicating the direction Bessie travels in during second $i$. If there are multiple routes minimizing the number of direction changes, output any.
There is only $1$ valid route, corresponding to the route $0→1→2→1→2→1→0$. Since this is the only possible route, it also has the minimum number of direction changes.
There are 3 possible routes:
$$
RRLRRLRLLL \\
RRRLRLLRLL \\
RRRLLRRLLL
$$
The first two routes have $5$ direction changes, while the last one has only $3$. Thus the last route is the only correct output.