AT_xmascon16_c Cutting Swiss Roll

[problemUrl]: https://atcoder.jp/contests/xmascon16noon/tasks/xmascon16_c 白うさと黒うさはクリスマスケーキとして長さ $ N $ cm のロールケーキを購入した．このロールケーキは場所によって甘さが異なり，各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) に対し，ケーキの左端から $ i-1 $ cm の場所から $ i $ cm の場所までの甘さは整数 $ A_i $ で表される． 白うさと黒うさは，このケーキのうちちょうど $ 1 $ cm を $ 2 $ 羽で一緒に食べ，残りの部分は冷蔵庫にしまおうと考えている．ケーキのどの部分を食べるかは以下のようにして決める． 1. まず白うさが，左端から $ k $ cm のところでケーキを $ 2 $ つに切り分ける．ここで $ k $ は $ 1 $ 以上かつケーキの長さ未満の整数であればなんでもよい． 2. 切り分けられた $ 2 $ つのケーキのうち，黒うさが好きな方をひとつを選んで冷蔵庫にしまう． この手順 1, 2 を終えたあとでケーキがまだ $ 2 $ cm 以上残っている場合，次は黒うさがケーキを切り分けて白うさが片方を冷蔵庫にしまう．こうして長さ $ 1 $ cm のケーキが残るまで，白うさと黒うさは交代しながら手順 1, 2 を繰り返し行う． 白うさはとにかく甘いケーキが好きなので，最終的に残るケーキの甘さが最大になるように行動したいと考えている．一方，黒うさはビターな味付けのほうが好きなので，最終的に残るケーキの甘さが最小になるように行動したいと考えている． 双方が最適な行動をとったとき，最終的に残るケーキの甘さを $ X $ とする．白うさの最適な行動，すなわち黒うさがどのように行動しても最終的に甘さ $ X $ 以上のケーキを必ず残せるような戦略を実装したプログラムを作成せよ ($ X $ は明示的に与えられないことに注意せよ)． ### Input & Output Format まず，ケーキの長さを表す整数 $ N $ が標準入力に与えられる．続いて，ケーキの甘さを表す $ N $ 個の整数 $ A_1 $, $ A_2 $, ..., $ A_N $ が順に標準入力に与えられる． その後，ケーキの切り分けが開始され，以下の入出力 1〜4 が繰り返される． 1. あなたのプログラムは，白うさがケーキを切る場所を表す整数 $ k $ を標準出力に出力する．これはケーキの左端から $ k $ cm の地点を切ることを意味する． - $ k $ は $ 1 $ 以上かつ現在のケーキの長さ未満でなければならない． 2. 文字 `L` または `R` が標準入力に与えられる．`L`, `R` はそれぞれ黒うさが切れ目より左・右の部分を冷蔵庫にしまったことを表す． - 黒うさのこの行動により残ったケーキが $ 1 $ cm になった場合，以降入力は与えられず，あなたのプログラムも直ちに終了せねばならない． 3. 黒うさがケーキを切る場所を表す整数 $ k' $ が標準入力に与えられる．これはケーキの左端から $ k' $ cm の地点を切ることを意味する． - $ k' $ は $ 1 $ 以上かつ現在のケーキの長さ未満である． 4. あなたのプログラムは，文字 `L` または `R` を標準出力に出力する．`L`, `R` はそれぞれ白うさが切れ目より左・右の部分を冷蔵庫にしまうことを表す． - 白うさのこの行動により残ったケーキが $ 1 $ cm になった場合，以降入力は与えられず，あなたのプログラムも直ちに終了せねばならない． 入出力例も参考にせよ．

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 5,000 $． - $ 1\ \leq\ A_i\ \leq\ 10^9 $． - $ A_i $ は整数． ### 採点 あなたのプログラムが以下に示す入出力のフォーマットに従った上で，最終的に残ったケーキの甘さが $ X $ 以上である場合，正答と見なされる． すべてのテストケースに正答すれば $ 100 $ 点が与えられる． ### 注意点 ケーキの長さが $ 1 $ cm になった後，**あなたのプログラムは直ちに終了しなければならない．** 終了しなかった場合のジャッジ結果は不定である．また，正しくない出力をした場合の結果も不定である（必ずしも `WA` になるとは限らない）． **出力した後に，出力をflushしなければならないことに注意せよ．flushしなかった場合，TLEとなることがある．** 各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: [ABC 019 D: 高橋くんと木の直径](http://abc019.contest.atcoder.jp/tasks/abc019_4)) を参考にするとよい． ### 入出力例 $ N=5,\ A\ =\ \{1,2,3,4,5\} $ ときの入出力例を示す． 入力 出力 説明 $ 5 $ $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ ケーキの長さ $ N $ と甘さ $ A $ が与えられている． $ 4 $ 白うさがケーキを左から $ 4 $ cm の点で切る． R 黒うさが右の部分を冷蔵庫にしまう． $ 1 $ 黒うさがケーキを左から $ 1 $ cm の点で切る． L 白うさが左の部分を冷蔵庫にしまう． $ 2 $ 白うさがケーキを左から $ 2 $ cm の点で切る． R 黒うさが右の部分を冷蔵庫にしまう． $ 1 $ 黒うさがケーキを左から $ 1 $ cm の点で切る． L 白うさが左の部分を冷蔵庫にしまう．この時点でケーキが $ 1 $ cm となるので応答は終了する．上記の応答例では最終的に甘さ $ 3 $ のケーキが残っている．このケースでは $ X\ =\ 3 $ (白うさと黒うさが双方ともに最適に行動したときに残るケーキの甘さが $ 3 $) であるため，上記の応答例は正答と見なされる．