ユウキ君は彼の友達3人とランドソルトランプで大富豪がしたいです。
ランドソルトランプのデッキには上から(と書かれたカード),(と書かれたカード),…,(と書かれたカード)の順で合計枚のカードが入ってます。
(つまりの場合、上から順に,,,と枚のカードが入ってます。)
このまま配り始めると最後にカードを受け得とる花子さんが凄く有利なのでユウキ君はカードを回シャッフルしました。
ユウキ君はシャッフルの方法を一つしか知りません(以下、この方法を「シャッフル」と表記します)。
具体的には長さ数列 が与えられた時、シャッフル毎に現在上から番目にあるカードのシャッフル後の位置は上から番目となります。
(つまり、の場合、デッキを初期状態から1回シャッフルするとデッキのカードは上からとなり、初期状態から2回シャッフルするとカードは上から
になります。)
回のシャッフルを終えた結果、ユウキ君が顔を上げると花子さんが鬼のような目でユウキ君を睨んでいました。
このままでは怒られてしまうかもと思ったユウキ君は追加で何回かシャッフルをして、デッキを初期の状態(上から)に戻そうと考えました。
ユウキ君のために最小であと何回シャッフルすればデッキを初期の状態に戻せるかを出力してください。
何回シャッフルしても初期状態に戻せないのであれば、
代わりにと出力してください。
・ (デッキの中のカードは最小で枚、最大で枚)
・はの倍数
・ (ユウキ君はユウキ君式シャッフルを既に最小で回、最大で回している)
・数列にはからの数字が各一回ずつ出現する
一行目には整数, が与えられる(はデッキ内のカードの枚数、は既にシャッフルした回数)
二行目には数列が与えられる
ユウキ君のために最小であと何回シャッフルすればデッキを初期の状態に戻せるかを出力してください。
何回シャッフルしても初期状態に戻せないのであれば、
代わりにと出力してください。
4 0 1 2 3 4
0
ユウキ君はシャッフルを一回もしてないので、カードは初期状態のままです。よって追加でシャッフルする必要はありません。
4 2 2 1 4 3
0
シャッフル一回目でカードは上からとなり、2回目で上からに戻ります。
これは初期状態と同じなのでやはり追加でシャッフルする必要はありません。
4 2 3 1 2 4
1
シャッフル一回目でカードは上からとなり、2回目で上からとなります。
回シャッフルするとに戻るので、追加で必要な最小回数1を出力します。