問題
n個の整数が書かれたキャンディーがある。
これらのキャンディーをくじ引き機に入れ、商品を買ったお客には３回くじ引きを引いてもらう。
そして、それらのキャンディーの中でキャンディーに書かれた数字の最も大きいキャンディーをお客にプレゼントし、 数字の最も小さいキャンディーをスタッフがなめる。
それ以外のキャンディーは再びくじ引き機の中に入れる。
これを繰り返した後、最後にくじ引き機の中に１つだけ残ったキャンディーは店長がなめる。
これは店長しか知らない話なのだが、実はキャンディーに書かれた数字はそのキャンディーの幸福度を表している。
このキャンディーをなめると幸福度の大きさによってはぴ☆はぴ☆になるので、店長は出来る限り数字の大きいキャンディーをなめたかった。
しかし今のくじ引き機はごく普通のくじ引き機であるため、店長がなめるキャンディーは運次第。
そこで、店長はくじ引き機を改良し、指定の順番でキャンディーが出てくるようにした。
FIFOという単語をご存じだろうか。
First In First Outの略で、要するに最初に入れたキャンディーが一番最初に出てくるという意味である。
待ち行列、Queueなどで調べると具体的にわかるだろう。
これにより、店長はキャンディーの出てくる順番を指定することが出来た。
このとき店長がなめることが出来るキャンディーの番号の最大値を求めよ。
なお、場合によっては最終的にキャンディーが２つくじ引き機の中に残っている状況がある
その場合はお客は３回くじ引きを引くことは出来ないので、ここでくじ引きは終了である。
このとき、店長はどちらのキャンディーもなめることができないので"NA"と出力すること。
入力
N h1 h2 . . . hN
1 行目にキャンディーの数を表す非負整数 N が与えられる。
2 行目からはi番目のキャンディーの番号の整数 hi が与えられる。
整数の名称がbになっていましたが、hiに修正しました。出力
店長がなめることができるキャンディーのうち、最も番号の大きい物を出力せよ。どのようにキャンディーを詰めても最後にキャンディーが２つ残ってしまう場合は"NA"と出力せよ。 出力の最後の改行を忘れないこと。
制約
全ての入出力ケースについて以下を満たす。
- 3 ≦ N ≦ 106
- 0 ≦ hi ≦ 106
部分点
テストケースのセットAは3≦N≦16であることが保証されている。このテストケースをとくと5点もらえる。
テストケースのセットBは3≦N≦103であることが保証されている。このテストケースをとくと10点もらえる。
テストケースのセットAとセットBはi ≠ jの時hi ≠ hjであるとが保証されている。このテストケースをとくと10点もらえる。
入出力例
入力例1
7 5 5 8 6 2 8 9
出力例1
8
解説
８のキャンディーを店長がなめるためにはくじ引き機に8,8,5,6,2,5,9の順番で詰める
まず、一人目の客は8,8,5を手に入れる。一番大きい数字は8で、一番小さい数字は5なので、8のキャンディーを１つ、お客にプレゼントし、5のキャンディーをスタッフがなめる。残った8のキャンディーをくじ引き機に詰める。
このとき、くじ引き機の中は6,2,5,9,8となっている。
二人目の客は6,2,5を手に入れる。一番大きい数字は6で、一番小さい数字は2なので、6のキャンディーを１つ、お客にプレゼントし、2のキャンディーをスタッフがなめる。残った5のキャンディーをくじ引き機に詰める
このとき、くじ引き機の中は9,8,5となっている。
二人目の客は9,8,5を手に入れる。一番大きい数字は9で、一番小さい数字は5なので、9のキャンディーを１つ、お客にプレゼントし、5のキャンディーをスタッフがなめる。残った8のキャンディーをくじ引き機に詰める
このとき、くじ引き機の中は8となっている。
最後に１つ残った８のキャンディーを店長がなめることができ、これが店長がなめることができるキャンディーの最大値である。
この並び以外にも８のキャンディーを店長がなめることができるキャンディーの並びは存在する。
入力例2
8 1 2 3 4 5 6 7 8
出力例2
NA
解説
この場合どのように並べても最終的に二つあまってしまう。この場合"NA"を出力する。
入力例3
7 26 83 53 68 40 84 15
出力例3
68