AT_xmascon16_c.Cutting Swiss Roll

白うさ和黒うさ买了一条长度为 $N$ 厘米的圣诞蛋糕卷。这条蛋糕卷的不同位置甜度各不相同，对于每个 $i$（$1 \leq i \leq N$），从蛋糕左端第 $i-1$ 厘米到第 $i$ 厘米的部分甜度用整数 $A_i$ 表示。

白うさ和黒うさ打算一起吃掉这条蛋糕卷中恰好 $1$ 厘米的部分，其余部分则放入冰箱保存。他们决定吃哪一部分蛋糕的方式如下：

1. 首先，白うさ在距离蛋糕左端 $k$ 厘米处将蛋糕切成两段。这里 $k$ 可以是任意大于等于 $1$ 且小于当前蛋糕长度的整数。
2. 在被切分出的两段蛋糕中，黒うさ选择自己喜欢的一段放入冰箱。

完成上述第 1、2 步后，如果蛋糕还剩下不少于 $2$ 厘米，则接下来由黒うさ切蛋糕，白うさ选择一段放入冰箱。如此交替进行，直到只剩下 $1$ 厘米的蛋糕为止。

白うさ非常喜欢甜的蛋糕，因此希望最终剩下的蛋糕甜度尽可能大。而黒うさ则喜欢苦味，因此希望最终剩下的蛋糕甜度尽可能小。

当双方都采取最优策略时，最终剩下的蛋糕甜度为 $X$。请你编写一个程序，实现白うさ的最优策略，即无论黒うさ如何选择，白うさ都能保证最终剩下的蛋糕甜度至少为 $X$（注意，$X$ 并不会直接给出）。

首先，标准输入给出一个整数 $N$，表示蛋糕的长度。接下来，输入 $N$ 个整数 $A_1, A_2, \ldots, A_N$，依次表示蛋糕每一厘米的甜度。

之后，蛋糕的切分过程开始，以下输入输出 1～4 会不断重复：

1. 你的程序输出一个整数 $k$，表示白うさ在距离蛋糕左端 $k$ 厘米处切蛋糕。
   • $k$ 必须是大于等于 $1$ 且小于当前蛋糕长度的整数。
2. 标准输入给出一个字符 L 或 R，分别表示黒うさ将切口左侧或右侧的部分放入冰箱。
   • 如果此操作后蛋糕只剩 $1$ 厘米，则后续不再输入，你的程序也应立即结束。
3. 标准输入给出一个整数 $k'$，表示黒うさ在距离蛋糕左端 $k'$ 厘米处切蛋糕。
   • $k'$ 必须是大于等于 $1$ 且小于当前蛋糕长度的整数。
4. 你的程序输出一个字符 L 或 R，分别表示白うさ将切口左侧或右侧的部分放入冰箱。
   • 如果此操作后蛋糕只剩 $1$ 厘米，则后续不再输入，你的程序也应立即结束。

请参考输入输出示例。

见上文输入输出流程描述。

限制

• $2 \leq N \leq 5,000$。
• $1 \leq A_i \leq 10^9$。
• $A_i$ 为整数。

评测

只要你的程序遵循上述输入输出格式，并且最终剩下的蛋糕甜度不小于 $X$，即认为答案正确。

所有测试点均正确时可得 $100$ 分。

注意事项

当蛋糕长度变为 $1$ 厘米后，你的程序必须立即结束。 若未结束，评测结果不确定。若输出不正确，结果也不确定（不一定是 WA）。

注意输出后必须刷新输出缓冲区，否则可能会 TLE。

各语言的输入输出方法可参考 AtCoder 以往题目（链接：ABC 019 D: 高桥くんと木の直径）。

输入输出示例

以 $N=5,\ A = \{1,2,3,4,5\}$ 为例，给出一次输入输出示例。

输入	输出	说明
5		蛋糕长度 $N$ 和甜度数组 $A$。
1
2
3
4
5
	4	白うさ在距离左端 $4$ 厘米处切蛋糕。
R		黒うさ将右侧部分放入冰箱。
1		黒うさ在距离左端 $1$ 厘米处切蛋糕。
	L	白うさ将左侧部分放入冰箱。
	2	白うさ在距离左端 $2$ 厘米处切蛋糕。
R		黒うさ将右侧部分放入冰箱。
1		黒うさ在距离左端 $1$ 厘米处切蛋糕。
	L	白うさ将左侧部分放入冰箱。此时蛋糕只剩 $1$ 厘米，程序应立即结束。

在上述交互中，最终剩下的蛋糕甜度为 $3$。此时 $X=3$（即双方最优时最终剩下的蛋糕甜度为 $3$），因此上述交互为正确答案。

由 ChatGPT 4.1 翻译