Tournament

Time Limit : 2 sec, Memory Limit : 262144 KB

A: トーナメント

問題

AOR イカちゃんとあなたは、トーナメント形式の卓球大会シングルスの部に偵察に来た。 全ての試合を録画したい AOR イカちゃんのために、あなたはこの大会で行われる試合数を求めてあげることにした。

この大会には $N$ 人の選手が参加しており、それぞれ $0, \dots , N - 1$ の背番号を持っている。 そのうち、 $M$ 人の選手が棄権し、試合には出場しなかった。

この大会の試合数は、以下のルールに基いて決定される。

  • シード選手は存在せず、任意の出場者が優勝するために必要な勝利回数は一定である。
  • 対戦相手が不在の場合は試合を行わず、出場した選手が勝利する。試合数にはカウントされない。
  • 優勝者が決まった段階で大会は終了する。
  • 一度試合に負けた人が再び試合をすることはない。つまり敗者復活戦や 3 位決定戦などは行わない。
  • なお、卓球台が 1 台しか無いため異なる試合が同時に行われることはなく、また各試合では必ず勝者が決まる (引き分けとなることはない)。

なお、トーナメントの定義は次のとおりである。 トーナメントは高さ $L = \log_2 N$ の完全二分木で表され、葉にあたる各頂点には参加者の背番号が書き込まれている。 根の深さを 0 とすると、 $i$ 回戦 ($1 \le i \le L$) では、 深さ $L - i$ の各頂点の子に書かれた番号の選手同士が試合を行い、その勝者の背番号をその頂点に書き込む。

制約

  • $2 \le N \le 2^8$
  • $0 \le M \le N - 1$
  • $0 \le a_i \le N - 1 \ (0 \le i \le M - 1)$
  • $N$ は 2 の累乗である。
  • $a_i \ (0 \le i \le M - 1)$ は相異なる

入力形式

入力は以下の形式で与えられる。

$N \ M$
$a_1$
$\vdots$
$a_M$

  • 1 行目には、参加者を表す整数 $N$ 、参加者のうち棄権した者の人数を表す整数 $M$ が与えられる。
  • 続く $M$ 行には、棄権して出場しなかった選手の番号を表す整数 $a_i$ が与えられる。

出力

この大会が終了するまでに行われる試合数を 1 行で出力せよ。また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

2 0

サンプル出力 1

1

最初の試合で優勝者が決まる。

サンプル入力 2

4 2
2
3

サンプル出力 2

1

Note

Commentary
 
Source: Ritsumeikan University Programming Camp 2017 , Day 1, Shiga, Japan, 2017-03-22