問題
高校入学後、プログラミング部に入部したタケ子さんは、次第にアルゴリズムの面白さにのめりこんでいきました。いまでは、２年生になったらプログラミング甲子園に出場してみたいと考えています。
あるとき、ソート・アルゴリズムについて学んだタケ子さんは、ソート・アルゴリズムを自分で設計してみました。タケ子さんが作ったソート・アルゴリズムでは、入力として要素の間に重複のない、１個以上の自然数からなる列が与えられたとき、以下の処理を実行します。
| 1. はじめに、列の先頭の要素を選ぶ。 2. 選んだ要素の直前に要素があるとき、選んだ要素とその直前の要素を比べる。直前の要素のほうが大きいなら、それを列の末尾の直後に移動させる(右図）。この操作を、選んだ要素が列の先頭になるか、選んだ要素よりその直前の要素の方が小さくなるまで続ける。 3.選んだ要素が列の末尾なら終了。そうでなければ、選んだ要素の直後の要素を新たに選び、2へ戻る。 タケ子さんはこのアルゴリズムがどのくらいの計算時間を必要とするか見積もるために、要素を列の末尾の直後に移動させる操作の回数を数えることにしました。 |  |
課題
列の情報を入力とし、要素を列の末尾の直後に移動させる操作の回数を報告するプログラムを作成せよ。
入力
N a1 a2 ... aN
１行目に列に含まれる要素の個数N(1≦N≦200000)が与えられる。２行目に列の要素ai(1≦ai≦109)が先頭から順番に与えられる。要素aiに重複はない。
時間制限
入力に対して、実行時間が３秒を超えてはならない。
出力
要素を列の末尾の直後に移動させる操作の回数を１行に出力する。
入出力例
入力例1
6 1 3 6 5 8 2
出力例1
10
入力例１では、要素の移動が行われるたびに、以下のように列が変化していく。
０回目： 1 3 6 5 8 2
１回目： 1 3 5 8 2 6
２回目： 1 3 5 2 6 8
３回目： 1 3 2 6 8 5
４回目： 1 2 6 8 5 3
５回目： 1 2 6 5 3 8
６回目： 1 2 5 3 8 6
７回目： 1 2 3 8 6 5
８回目： 1 2 3 6 5 8
９回目： 1 2 3 5 8 6
１０回目： 1 2 3 5 6 8
入力例2
4 3 2 1
出力例2
6