P15783 [JAG 2025 Summer Camp #3] Ants Collision

在一条数轴上有 $N$ 只蚂蚁。第 $i$ 只蚂蚁初始位于坐标 $i$ 处，并且保持静止。每只蚂蚁面朝右（正方向）或左（负方向），但其初始朝向未知。 在时刻 $0$，每只蚂蚁开始以单位时间 $1$ 的速度移动。每当两只蚂蚁碰撞（即占据同一位置）时，它们会调转方向，朝相反方向移动。 到时刻 $10^{100}$ 为止，第 $i$ 只蚂蚁恰好与其他蚂蚁发生了 $A_i$ 次碰撞。 请判断是否存在一种蚂蚁的初始朝向分配方案，使得这些碰撞次数成立。如果存在这样的方案，请构造一种。

输入包含多个测试用例。 第一行包含一个整数 $T$（$1 \leq T \leq 10000$），表示测试用例的数量。 接下来是 $T$ 个测试用例。每个测试用例的格式如下： $$ \begin{aligned} &N \\ &A_1 \ A_2 \ \ldots \ A_N \end{aligned} $$ 对于每个测试用例，第一行包含一个整数 $N$（$1 \leq N \leq 300000$），表示蚂蚁的数量。 下一行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$0 \leq A_i \leq 10^9$），每个整数表示对应蚂蚁到时刻 $10^{100}$ 为止与其他蚂蚁碰撞的次数。 此外，所有测试用例的 $N$ 之和不超过 $300000$。

输出 $T$ 行。对于每个测试用例，判断是否存在满足题目所述条件的蚂蚁初始朝向分配方案。 - 如果不存在这样的方案，输出 "No"。 - 如果存在这样的方案，输出一个长度为 $N$ 的字符串，由字符 'L' 和 'R' 组成，其中第 $i$ 个字符为 'L' 表示第 $i$ 只蚂蚁初始面朝左（负方向），为 'R' 表示初始面朝右（正方向）。 如果存在多种方案，输出任意一种均可。

翻译由 DeepSeek V3.2 完成