[R58E]排序 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给出一个长度为偶数 $n$ 的排列$^{\dagger}$ $a$，你可以对它进行至多 $2 \times n$ 次操作。

对于每次操作:

1.将 $a_1 \dots a_{\frac{n}{2}}$ 加入初始为空的队列 $l$。将 $a_{\frac{n}{2}+1} \dots a_{n}$ 加入初始为空的队列 $r$。

2.新建一个数组 $b$，进行 $n$ 次小操作。

3.每次小操作，弹出 $l,r$ 两队列中任意一个不为空队列的队首，放入 $b$ 数组最后面。

4.将 $a$ 赋值为 $b$。

现在请你构造一组操作方案使得最后 $a$ 单调递增，即为 $1 ,2\dots n$。

$^{\dagger}$：长度为 $n$ 的排列是指一个包含 $1$ 到 $n$ 中每个正整数各恰好一次的序列。例如，$[2, 3, 1, 5, 4]$ 是一个长度为 $5$ 的排列，而 $[1, 2, 2]$ 和 $[1, 3, 4]$ 则不是。

格式

输入格式

第一行包含一个正整数 $n$，表示数组的长度。

第二行包含 $n$ 个数 $a_1 ,a_2 ,a_3 ,\cdots a_n$，表示 $a$ 数组。

输出格式

第一行输出一个非负整数 $k$。

第 $2$ 到 $k+1$ 行，每行输出一个长度为 $n$ 的字符串，保证其中包含字符 $l,r$ 的个数相同，第 $i$ 个字符为你选择弹出队首的队列。

注意：$k$ 必须小于等于 $2 \times n$。

样例

样例输入 #1

4
1 4 2 3

样例输出 #1

1
lrrl

样例输入 #2

6
1 3 2 6 5 4

样例输出 #2

3
llrlrr
lrrlrl
llrrlr

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	特殊性质
$1$	$20$	特殊性质 A
$2$	$80$	无

特殊性质 A：$i \leq \frac{n}{2}$ 时，$a_i = i \times 2 - 1$，$\frac{n}{2}< i \leq n$ 时，$a_i = (i - \frac{n }{2}) \times 2$。

对于 $100\%$ 的数据，$2 \leq n\leq 10^3$，$1 \leq a_i \leq n$，且 $a_i$ 互不相同。