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: 高桥くんと木の直径](http://abc019.contest.atcoder.jp/tasks/abc019_4)）。 ### 输入输出示例 以 $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 翻译