No.123 カードシャッフル

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 242
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

3 ProblemId : 284 / 出題時の順位表

問題文

$1$から$N$までの数字を描いたカードが各$1$枚、合計$N$枚あります。
カードは$1$から$N$まで順に上から積まれています。いちばん上が$1$のカードです。
上から$A_i$番目のカードを抜いていちばん上に積みます。これを$1$回のシャッフルとします。
$M$回のシャッフルが行われた後にいちばん上にあるカードの数字はいくつでしょう?

入力

$N$ $M$
$A_1\,A_2\dots\,A_m$

$N$はカードの最大の数字であり枚数。($1 \le N \le 50$)
$M$はシャッフルの回数。($1 \le M \le 100000$)
$A_i$は$i$回目のシャッフルで上から$A_i$番目のカードを抜き上に積むことをあらわす。($1 \le A_i \le N$)

出力

$M$回のシャッフルを行った後でいちばん上にあるカードの数字を答えよ。
最後に改行を忘れずに。

サンプル

サンプル1
入力
3 1
2
出力
2

最初に1から3までの3枚のカードが積まれています。上から1,2,3の順です。
1回目のシャッフルで上から2番目の2の数字のカードを抜いていちばん上に積みます。
よって、いちばん上のカードは2になります。

サンプル2
入力
3 2
3 2
出力
1

最初に1から3までの3枚のカードが積まれています。上から1,2,3の順です。
1回目のシャッフルで上から3番目の3の数字のカードを抜いていちばん上に積みます。
カードは上から順に3,1,2の順で積まれています。
2回目のシャッフルで上から2番目の1の数字のカードを抜いていちばん上に積みます。
よって、いちばん上のカードは1になります。

サンプル3
入力
4 4
1 1 1 1
出力
1

最初に1から4までの4枚のカードが積まれています。上から1,2,3,4の順です。
上から1番目のカードを抜いて上に積むシャッフルを4回行います。
カードの順番はまったく動きません。よって、いちばん上のカードの数字は1です。

サンプル4
入力
10 8
6 10 4 2 7 1 4 3
出力
10

提出ページヘ