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

Img 04 03 下記の問題をプログラミングしてみよう!

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

パイザ図書館には 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 となります。

▼ 下記回答欄にコードを記入してみよう

入力される値

入力は以下のフォーマットで与えられます。

N
a_1 a_2 ... a_N

・1 行目に本の冊数を表す整数 N が与えられます。
・2 行目に、 1 番目の本の ID を表す整数 a_1、 2 番目の本の ID を表す整数 a_2、 ...、 N 番目の本の ID を表す整数 a_N がこの順に半角スペース区切りで与えられます。
・入力は合計で 2 行となり、末尾に改行が 1 つ入ります。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

本の交換をする回数を整数で出力してください。

出力の最後に改行を入れ、余計な文字、空行を含んではいけません。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 100,000
・1 ≦ a_i ≦ N (1 ≦ i ≦ N)
・各 j, k (1 ≦ j, k ≦ N) について j ≠ k のとき a_j ≠ a_k

入力例1

5
5 4 3 2 1

出力例1

2

入力例2

10
8 7 9 1 5 6 2 10 4 3

出力例2

6

解答欄

上記の問題の解答コードを下記入力欄に記入し提出してください。

複数のテストケースでテスト致しますので、 サンプル入力だけでなく入力値を可変させてデバッグしていただく事をお勧めいたします。

標準入力の値の取得方法は下記ページのサンプルコードを参照ください。

解答欄

ページの先頭へ戻る