Search

Time Limit : 1 sec, Memory Limit : 65536 KB

Search

「探索」とは、たくさんの情報の中から望みの情報を得る操作のことです。身近な例では、合格発 表の時の「たくさんの受験番号から自分の受験番号を見つける」ことや、電話帳から「会津太郎さん の電話番号を見つける」ときなどがあります。この探索という操作はコンピュータの分野でも広く用 いられています。

探索の方法は沢山あります。探索の対象となるデータが、小さい順(または大きい順)に並べられ ている場合に使うことができる探索の方法を考えます。

小さい順(または大きい順)に並べられているデータ列の中央に位置する値と目的の値との大小関 係を用いて、中央に位置する値から前半部分を探索範囲にするか後半部分を探索範囲にするかを決め ることで、探索の範囲を絞っていく方法があります。手順は以下のようになります。

  1. データの列の全体を探索の範囲とします。
  2. 探索の範囲の中央に位置する値を調べます。
  3. 目的の値と中央に位置する値が一致すれば探索を終了します。
  4. 目的の値と中央に位置する値よりも小さければ前半部分を探索の範囲とし、大きければ後半部分を探索の範囲として2.へ戻ります。

以下は上述した探索の方法の例です。この例での目的の値は51です。それぞれのデータには番号 (index)が振られており、この番号は0から始まっています。

ステップ1: 最初は番号0~6全体を探索の範囲としま す。

ステップ2:探索の範囲の中央に位置する 値を調べます。ただし、「中央に位置する 値」とは、(左側の番号+右側の番号)を2 で割った番号の位置にある値とします。つ まり、この場合、(0 + 6) ÷ 2 を計算 し、番号3にある値(36)が中央に位置する 値となります。

ステップ3:目的の値(51)と中央に位置す る値(36)を比較します。

ステップ4:ステップ3の結果から、目的 の値は中央に位置する値より大きいので、 後半部分にあたる番号4 (中央に位置する 値の隣)以降を探索の範囲とします。 同様の手順で探索の範囲の中央に位置する 値を調べ、目的の値が中央に位置する値よ り小さければ前半部分を探索の範囲とし、 大きければ後半部分を探索の範囲として、 探索の範囲を小さくしていきます。(ステ ップ2~ステップ4の繰り返し) 目的の値が中央に位置する値と一致する か、探索の範囲がつきてしまった時に探索 を終了します。

n個の数値の配列を入力とし、目的の値と中央に位置する値を比較した回数を出力するプログラム を作成してください。ただし、中央に位置する値の番号を計算したとき、割り切れない場合は、小数 点以下を切り捨てた値をその番号とすることとします。また、n は 1以上 100以下とし、入力される 値は 1以上 100,000以下の整数とします。さらに、与えられるデータ列は小さい順に整列されている ものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されま す。 各データセットは以下のとおりです。

 1行目  数値の数 n(整数)
 2行目  1つ目の数値(整数)
 3行目  2つ目の数値
       :
       :
 n+1行目 n個目の数値
 n+2行目 探索する値(整数)

Output

入力データセット毎に探索が終わるまでの比較回数(整数)を出力します。

Sample Input

7
11
15
23
36
51
61
86
51
4
1
2
3
5
4
0

Output for the Sample Input

3
3

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