配点：$100$ 点

問題文

いろとくんは、いなり寿司が食べたいです。

そこで，回転寿司に行きました．いろとくんの他に客はいないようです．

それぞれ $0$ から $N-1$ までの番号がついた $N$ 個の台座とお寿司がレーンに乗って流れています．
はじめ，台座 $i$ にはお寿司 $i$ が $1$ つ置かれています．$\scriptsize (0 \leq i < N)$

いろとくんの手元へ $i$ 番目に流れてくる台座は，台座 $i \bmod N$ です．(はじめを $0$ 番目とします．)
また，$(0, 1, \ldots, N-1)$ の順列 $(P_0, P_1, \ldots, P_{N-1})$ について，お寿司 $i$ の味は $P_i$ です．$\scriptsize (0 \leq i < N)$

いろとくんは，食べたいお寿司が手元に流れてくるたびに，そのお寿司を台座から取って食べます．したがって，同じ味のお寿司は $1$ 度まで食べられます．

いろとくんは特殊なので，味 $0$ から味 $N-1$ まで，$N$ 個のお寿司を味の昇順に食べます．

いろとくんが味 $N-1$ のお寿司を食べ終わったとき，レーンは完全に何周していますか？
求めてください．

なお，いろとくんが，手元へ $i$ 番目に流れてきた台座に乗っているお寿司を食べ終わったとき，レーンは完全に $\left\lfloor \frac{i}{N} \right\rfloor$ 周しています．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq N$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 10^5$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

出力

答えを出力せよ．

サンプル

1
5
0 2 3 1 4

1

• $1$ 周目で，味 $0, 1$ のお寿司を，味の昇順に食べることができます．
• $2$ 周目で，残った味 $2, 3, 4$ のお寿司を，味の昇順に食べることができます．

したがって，味 $4$ のお寿司を食べ終わった時点では，レーンは完全に $1$ 周しています．

1
5
0 1 2 3 4

0

レーンが一周し切る前にすべてのお寿司を味の昇順に食べることができます．

2
5
4 3 2 1 0
1
0

4
0

ところで，お目当てのいなり寿司は，いつまで経っても流れてこないようでした．