第７回日本情報オリンピック　予選３

2007年12月16日
情報オリンピック日本委員会

問題

次のような2人で行うカードゲームがある．

• このゲームでは， 1から2nまでの各整数が書かれた全部で2n枚のカードを使用する． ここで，nは1以上100以下の整数である．
• このカードを2人にn枚ずつ配る．
• 次のルールに従って交互にカードを1枚ずつ場に出す．
  • 場にカードが出ていないならば， 好きなカードを出すことができる．
  • 場にカードが出ているならば， 最後に場に出たカードよりも大きい数の書かれたカードを出すことができる．
  • カードが出せる場合は，必ず場にカードを出す必要がある．
  • 出せるカードが無い場合はパスとなり，相手の番になる． このとき，場に出ているカードは無くなる．
• ゲームは場にカードが出ていない状態で始める．
• どちらかの手持ちのカードが無くなった時点でゲームは終了する．
• ゲーム終了時に相手の持っているカードの枚数を得点とする．

太郎と花子は， このゲームで対戦することになった． ゲームは太郎の番から始める． 2人は共に， 出すことのできるカードのうち必ず一番小さい数が書かれたカードを出すことにしている．

太郎に配られるカードが入力されたとき， 太郎と花子の得点を出力するプログラムを作成せよ．

入力

入力は n+1 行ある． 1行目には整数nが書かれている． 2行目からn+1行目までの各行には整数が1つずつ書かれており， 太郎に配られるカードに書かれた整数を表す．

出力

提出する出力ファイルは2行からなる． 1行目には太郎の得点を， 2行目には花子の得点を出力せよ．

入出力例

5
1
7
9
6
10
  

10
8
7
14
18
4
11
3
17
5
19
   

3
0
   

2
0
   

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．

テストデータ