题目描述

农夫 Nhoj 把 Bessie 丢在了一个荒无人烟的地方！在时间 $t=0$ 时，Bessie 位于无限数轴的 $x=0$ 处。她疯狂地寻找出口，每秒向左或向右移动 1 个单位。然而，实际上并没有出口，在 $T$ 秒后，Bessie 回到了 $x=0$，疲惫且无奈。

农夫 Nhoj 试图追踪 Bessie，但他只知道 Bessie 穿过 $x=0.5,1.5,2.5, \cdots ,(N-1).5$ 的次数，由数组 $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 从未到达 $x>N$ 或 $x<0$。

特别地，Bessie 的路线可以用一个长度为 $T= \sum\limits_{i=0}^{N-1}A_i$ 的 $L$ 和 $R$ 字符串表示，其中第 $i$ 个字符表示 Bessie 在第 $i$ 秒移动的方向。方向变化的次数定义为 $LR$ 出现的次数加上 $RL$ 出现的次数。

请帮助农夫 Nhoj 找到任何一个与 $A$ 一致且方向变化次数最少的 Bessie 的路线。保证至少存在一条有效路线。

输入格式

第一行包含 $N$。第二行包含 $A_0,A_1,\cdots ,A_{N-1}$。

输出格式

输出一个长度为 $T=\sum\limits_{i=0}^{N-1}A_i$ 的字符串 $S$，其中 $S_i$ 是 L 或 R，表示 Bessie 在第 $i$ 秒的移动方向。如果有多条路线能使方向变化次数最少，输出任意一条。

输入输出样例 #1

输入 #1

2
2 4

输出 #1

RRLRLL

输入输出样例 #2

输入 #2

3
2 4 4

输出 #2

RRRLLRRLLL

说明/提示

示例 1 的解释

只有 1 条有效路线，对应的路线是 $0 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 0$。由于这是唯一可能的路线，因此它也具有最少的方向变化次数。

示例 2 的解释

有 3 条可能的路线：

RRLRRLRLLL
RRRLRLLRLL
RRRLLRRLLL

前两条路线有 5 次方向变化，而最后一条只有 3 次。因此最后一条路线是唯一正确的输出。

评分

• 输入 $3-5$：$N \le 2$
• 输入 $3-10$：$T=A_0+A_1+ \cdots +A_{N-1} \le 5000$
• 输入 $11-20$：无额外约束。

题面翻译由 ChatGPT-4o 提供。