A Pair of Prizes

Time Limit : 1 sec, Memory Limit : 65536 KB

おそろいの景品

ジョウ君とヤエさんは仲の良いカップルです。ジョウ君はカプセル玩具自販機(ガチャポン)の景品を集めており、二人で出かけたときも、ガチャポンを見つけると何度かやってみるほどの熱の入りようです。ヤエさんは楽しそうなジョウ君をそばで見ているだけでしたが、ジョウ君の今度の誕生日プレゼントにガチャポンの景品をひとつあげることにしました。ヤエさんはガチャポン自体にはあまり興味がわきませんでしたが、できればジョウ君とおそろいの景品が欲しいと思っています。

ヤエさんがやってみようと思うガチャポンは、1回のチャレンジで景品がひとつ出ます。品切れのものも含め景品が何種類あるのかと、それぞれの景品がいくつ残っているのかはわかります。しかし、1回のチャレンジでどの景品が出るかはわかりません。そこで、景品が出る順番にかかわらず、ヤエさんが同じ景品を必ず2つ得るために最低限必要なチャレンジの回数を出力するプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ1つの行で示される。各データセットは以下の形式で与えられる。

N
k1 k2 ... kN

各データセットは2行であり、1行目に景品が何種類あるかを表す整数N(1 ≤ N ≤ 10000)が与えられる。続く1行に各景品がいくつ残っているのかを表す整数ki(0 ≤ ki ≤ 10000)が与えられる。

データセットの数は100を超えない。

出力

データセットごとに、同じ景品を必ず2つ得るために最低限必要なチャレンジの回数を出力する。ただし、不可能な場合はNAと出力する。

入力例

2
3 2
3
0 1 1
1
1000
0

出力例

3
NA
2

1つ目のデータセットでは、運良く1種類目か2種類目の景品が連続で出て2回で済む可能性はあるが、同じ種類の景品を必ず2つ得るためには3回チャレンジする必要がある。
2つ目のデータセットでは、2つ以上残っている景品がもともと無いので不可能である。
3つ目のデータセットでは、景品は1種類だけなので2回のチャレンジでその景品が必ず2つ得られる。


Source: PC Koshien 2013, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2013-9-14
http://www.pref.fukushima.jp/pc-concours/