题目描述

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=0.5,1.5,2.5, \cdots ,(N−1).5$, given by an array $A_0,A_1, \cdots ,A_{N−1} (1 \le N \le 10^5, 1 \le A_i \le 10^6, \sum A_i \le 10^6)$. Bessie never reaches $x>N$ nor $x<0$.

In particular, Bessie's route can be represented by a string of $T= \sum\limits_{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,\cdots ,A_{N−1}$.

输出格式

Output a string $S$ of length $T=\sum\limits_{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.

题目大意

奶牛贝西开始在一条数轴上原点的位置，每次会向左或向右移动一个单位长度，最后回到了原点。

给定贝西经过 $0.5,1.5,\ldots,(N-1)+0.5$ 的次数（用数组 $A$ 表示，$A_i$ 表示经过 $i+0.5$ 的次数）。

请构造出一条可能的移动路径（由 $\texttt{L}$ 和 $\texttt{R}$ 构成，表示向左 / 向右走），使得中途改变方向的次数尽量少。

题目保证有解，若有多解，输出任意一组解即可。

翻译自

2
2 4

RRLRLL

3
2 4 4

RRRLLRRLLL

提示

Explanation for Sample 1

There is only $1$ valid route, corresponding to the route $0 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 0$. Since this is the only possible route, it also has the minimum number of direction changes.

Explanation for Sample 2

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.

Scoring

• Inputs $3-5$: $N \le 2$
• Inputs $3-10$: $T=A_0+A_1+ \cdots +A_{N−1} \le 5000$
• Inputs $11-20$: No additional constraints.