The Lonely Girl's Lie

Time Limit : 2 sec, Memory Limit : 65536 KB

寂しがり屋のついた嘘

パケットモンスターというゲームがあります。モンスターを捕まえ、育て、戦わせたり交換したりするゲームで、日本中で大流行しています。もちろん、わたしのクラスでも。だからわたしもこのゲームでみんなと遊べるようにモンスターを育てているけど、悲しいことに対戦する相手がいません。わたしは積極的に人に話しかけるのが得意なタイプではないからです。だから今日も、クラスメイトが誘ってくれるのを待ちながら、独り寂しくモンスターのレベルを上げています。

そしてついに、待ち望んでいた瞬間が訪れました。クラスメイトの一人が対戦しないかとわたしに話を持ちかけてきたのでした。彼女は自慢気に、彼女のモンスターたちを見せてくれました。

一般的なパケットモンスターの対戦ルールでは、各プレイヤーがそれぞれN 匹のモンスターを用意し、互いに1 匹ずつ戦わせます。各モンスターには成長の度合いを示す「レベル」という数値があり、レベルが大きいモンスターが必ず勝ちます。同レベルのときは引き分けです。一度戦ったモンスターは、それ以上戦わせることができません。こうして一対一の戦いをN 回行ったあと、過半数の勝利を収めたプレイヤーが勝者となります。

わたしは、彼女のモンスターを見た瞬間、嫌な予感がしました。彼女のモンスターはどれも、とても強そうなのです。わたしと戦ってくれるのなら負けてもかまいません。でも、あまりにもひどい負け方をしたら、"こいつと戦っても面白くないな"とか思われて、もう遊んでくれなくなるんじゃないかな。それは、とても嫌です。だから、
      「ごめん、わたしまだモンスターをN 匹持ってなくて」

嘘をつきました。

N 回勝負では勝ち目がなくても、それより少ない数のモンスターで勝負する特別ルールなら、もしかしたら勝てるかもしれません。さっきは負けたってかまわないと言ったけど、やっぱり勝てたら嬉しいです。

彼女はこの特別ルールを受け入れてくれました。つまり、二人が持っているモンスターからお互いに k 匹選んで一匹ずつ順番に戦わせ、過半数の(つまり、k/2 より大きな数の) 勝利を収めた方が勝ちとなります。

さっきわたしは、彼女のモンスターのレベルを知ってしまいました。彼女がどのモンスターを選び、どんな順番で出してくるのかはわかりません。でも、対戦させるモンスターの数kをわたしがうまく決めれば、彼女がどんな選択をしようとわたしが勝つことができるかもしれません。

皆さんにお願いです。モンスターの数 N と、二人が持っているモンスターのレベルを入力すると、彼女がどんな選択をしようとわたしが勝てるような最小のモンスターの数 k を出力するプログラムを作成して下さい。

入力

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

N
a1 a2 ... aN
b1 b2 ... bN

1行目にモンスターの数 N (1 ≤ N ≤ 40000) が与えられる。2行目に自分のモンスターのレベル ai (1 ≤ ai ≤ 100000) が1つの空白区切りで与えられる。3行目にクラスメイトのモンスターのレベル bi (1 ≤ bi ≤ 100000) が1つの空白区切りで与えられる。

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

出力

データセットごとに、k (1 ≤ k < N) が存在すれば最小値を1行に出力する。もし、k が存在しないか、k が N に等しければ NA と出力する。

入力例

10
4 9 1 9 5 9 2 3 2 1
8 7 6 5 10 5 5 4 7 6
5
4 3 2 5 1
4 4 4 4 4
4
4 1 3 2
4 3 2 1
0

出力例

3
1
NA

1つ目のデータセットでは、わたしは3匹での対戦を提案し、レベルが [9, 9, 9] のモンスターを選べば良い。相手のレベル 10 以外のどのモンスターにも勝てるので、少なくとも2勝できる。2匹での対戦では 1勝1敗になる可能性があり、これは過半数の勝利とは言えないので、2 は答えにならない。

2つ目のデータセットでは、わたしは最強のモンスターを1匹選べば良い。

3つ目のデータセットでは、わたしがどの k 匹を選び、どの順番で出したとしても、彼女が全く同じモンスターを同じ順番で出してきて引き分けになる可能性がある。したがって、「彼女がどんな選択をしようとわたしが勝つことができる」とは言い切れない。


Source: PC Koshien 2012 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2012-11-10
http://www.pref.fukushima.jp/pc-concours/