問題１ - 問題２ - 問題３ - 問題４ - 問題５ - 問題６
NPCA(Nokotta Pan wo kakete Chotto ookimeno Amidakuji)をすることになった。
あみだくじ作りを任された snuke はどうしてもパンが欲しかったので、必ず自分が「当たり」を引くようなあみだくじを作ることにした。
方法は下記の通りである。
・まずは適当に N 本の縦棒と M 本の横棒を引き、一番左の縦棒の下端に「当たり」の印を付けておく。
・N - 1 人に好きな別々の縦棒を選んでもらい、上端に名前を書いてもらう。
・１本残った縦棒の上に自分の名前を書く。
・自分の名前を書いた縦棒からあみだくじをたどっていくと「当たり」にたどりつくように、0本以上 M本以下の横棒を消す。
不正がばれにくくなるようにするために、なるべく多くの横棒を通って「当たり」にたどりつくようにしたい。
最適な横棒の消し方をした時に、snuke が名前を書いた場所から「当たり」まであみだくじをたどる際に通る横棒の本数を出力するプログラムを作成せよ。
例えば下図（Sample input 1に対応している）の場合、横線を消さなくとも「当たり」を引くことは出来るが、その際に通る横棒の本数は３である。
しかし、下図右のように２本の横棒を消すと、５本の横棒を通って「当たり」にたどりつくことができるので、この例の場合は 5 を出力する。
なお、適切な横棒を消すことにより必ず snuke は「当たり」を引くことが出来るものとし、どの２本の横棒も同じ高さの位置にはないものとする。
１行目には、N, M, snukeが名前を書いた縦棒が左から何本目かを表す数 K が空白を区切りとして書かれている。
続く M 行には横棒の情報が、あみだくじ上の位置が上のものから順に、１つの数 X として書かれている。
X は、左から X 番目の縦棒と 左から X+1 番目の縦棒とをつないでいることを表している。
最適な横棒の消し方をした時に、snuke が名前を書いた場所から「当たり」まであみだくじをたどる際に通る横棒の本数を１行に出力せよ。
1 ≦ X < N ≦ 10,000
1 ≦ M ≦ 100,000
ーSample input 1ー
4 7 2
1
2
3
3
2
1
1
ーSample output 1ー
5
ーSample input 2ー
2 1 1
1
ーSample output 2ー
0