本の整理 (paizaランク A 相当)

あなたはパイザ図書館で働く図書館員です。

パイザ図書館には N 冊の蔵書があります。この蔵書はすべて 1 段からなる本棚で管理されています。そして、それぞれの本には 1 から N までの相異なる整数の ID がついています。本棚の本は ID 順に並んでいます。

しかし、ある日、あなたが蔵書の点検をしていると、本棚の本がバラバラに並べられていることに気づきました。



そこで、あなたは、次のルールに従って本を並び替えることにしました。

次の手順を N 回繰り返す。

1. i (1 ≦ i ≦ N) 回目の手順では、まず本棚の左から i 番目の位置に立つ。
2. 左から i 番目の位置にある本から、本棚の右端にある本までのうち、最も ID が小さい本の位置を歩きながら見つける。この位置を j とする。
3. i = j なら、何もしない。 i ≠ j なら、i 番目の本と j 番目の本を入れ替える。


本を取り出して入れ替えるのには時間がかかります。そこで、このルールに従って本を整理するときに、何回本を入れ替える必要があるのかを計算してください。

例)

5 冊の本が、本棚に次の順番で並んでいたとします。ただし、数字はそれぞれの本の ID を表します。

5 4 3 2 1

このとき、ルールに従うと、次のように本が整理されます。

i = 1 のとき (1 番目の本と 5 番目の本の位置が入れ替わる)

1 4 3 2 5

i = 2 のとき (2 番目の本と 4 番目の本の位置が入れ替わる)

1 2 3 4 5

i = 3 のとき

1 2 3 4 5

i = 4 のとき

1 2 3 4 5

i = 5 のとき

1 2 3 4 5

本の交換は i = 1 のときと i = 2 のときのみ起こっているので、このときの出力は 2 となります。