IOI 王国では，王女である JOI 姫の誕生日を祝って舞踏会が開かれるようになった．
舞踏会には 人の貴族が参加する予定である． は奇数である．貴族には 1 から までの番号が付けられている．それぞれの貴族には踊りのうまさという整数が定められており，貴族 () の踊りのうまさは である．
舞踏会では JOI 姫を含む 人で 2 人ずつ組を作って踊る．IOI 王国では，上級者が初級者を補助できるように，伝統的に以下の方法で踊りの組を決定している．
- 最初に， 人の貴族が 1 列に並ぶ．
- 列に並んでいる貴族が 1 人になるまで，以下の操作を繰り返す．
- 列の先頭から 3 人の貴族の踊りのうまさを調べる．
- その 3 人の貴族の中で，最も踊りのうまさが大きい貴族を A とおく．ただし，複数いる場合は，最も踊りのうまさが大きい貴族の中で，最も番号の小さい貴族を A とおく．
- その 3 人の貴族の中で，最も踊りのうまさが小さい貴族を B とおく．ただし，複数いる場合は，最も踊りのうまさが小さい貴族の中で，最も番号の大きい貴族を B とおく．
- A と B が列から抜けて組になる．
- 残った 1 人は列の最後尾に移動する．
- 最終的に残った 1 人が JOI 姫と組になる．
貴族 1 から貴族 () の 人の貴族については，すでに初期状態で列の何番目に並ぶかが決まっている．残りの 人の貴族の並び方は国王が自由に決めることができる．
JOI 姫は踊りを学んだばかりなので，国王は JOI 姫と組になる貴族の踊りのうまさをできるだけ大きくしたいと考えている．JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めよ．
課題
それぞれの貴族の踊りのうまさと， 人の貴族の初期状態で並ぶ場所が与えられたとき，JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めるプログラムを作成せよ．
