高校入学後、プログラミング部に入部したタケ子さんは、次第にアルゴリズムの面白さにのめりこんでいきました。いまでは、2年生になったらプログラミング甲子園に出場してみたいと考えています。
あるとき、ソート・アルゴリズムについて学んだタケ子さんは、ソート・アルゴリズムを自分で設計してみました。タケ子さんが作ったソート・アルゴリズムでは、入力として要素の間に重複のない、1個以上の自然数からなる列が与えられたとき、以下の処理を実行します。
タケ子さんはこのアルゴリズムがどのくらいの計算時間を必要とするか見積もるために、要素を列の末尾の直後に移動させる操作の回数を数えることにしました。
列の情報を入力とし、要素を列の末尾の直後に移動させる操作の回数を報告するプログラムを作成せよ。
入力は以下の形式で与えられる。
N a1 a2 ... aN
1行目に列に含まれる要素の個数 N (1 ≤ N ≤ 200000) が与えられる。2行目に列の要素 ai (1 ≤ ai ≤ 109) が先頭から順番に与えられる。要素 ai に重複はない。
要素を列の末尾の直後に移動させる操作の回数を1行に出力する。
6 1 3 6 5 8 2
10
入力例1では、要素の移動が行われるたびに、以下のように列が変化していく。
0回目: 1 3 6 5 8 2 1回目: 1 3 5 8 2 6 2回目: 1 3 5 2 6 8 3回目: 1 3 2 6 8 5 4回目: 1 2 6 8 5 3 5回目: 1 2 6 5 3 8 6回目: 1 2 5 3 8 6 7回目: 1 2 3 8 6 5 8回目: 1 2 3 6 5 8 9回目: 1 2 3 5 8 6 10回目: 1 2 3 5 6 8
4 4 3 2 1
6