Sort

Time Limit : 3 sec, Memory Limit : 262144 KB

ソート

高校入学後、プログラミング部に入部したタケ子さんは、次第にアルゴリズムの面白さにのめりこんでいきました。いまでは、2年生になったらプログラミング甲子園に出場してみたいと考えています。

あるとき、ソート・アルゴリズムについて学んだタケ子さんは、ソート・アルゴリズムを自分で設計してみました。タケ子さんが作ったソート・アルゴリズムでは、入力として要素の間に重複のない、1個以上の自然数からなる列が与えられたとき、以下の処理を実行します。

  1. はじめに、列の先頭の要素を選ぶ。
  2. 選んだ要素の直前に要素があるとき、選んだ要素とその直前の要素を比べる。直前の要素のほうが大きいなら、それを列の末尾の直後に移動させる(図)。この操作を、選んだ要素が列の先頭になるか、選んだ要素よりその直前の要素の方が小さくなるまで続ける。
  3. 選んだ要素が列の末尾なら終了。そうでなければ、選んだ要素の直後の要素を新たに選び、2 へ戻る。


タケ子さんはこのアルゴリズムがどのくらいの計算時間を必要とするか見積もるために、要素を列の末尾の直後に移動させる操作の回数を数えることにしました。


列の情報を入力とし、要素を列の末尾の直後に移動させる操作の回数を報告するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N
a1 a2 ... aN

1行目に列に含まれる要素の個数 N (1 ≤ N ≤ 200000) が与えられる。2行目に列の要素 ai (1 ≤ ai ≤ 109) が先頭から順番に与えられる。要素 ai に重複はない。

Output

要素を列の末尾の直後に移動させる操作の回数を1行に出力する。

Sample Input 1

6
1 3 6 5 8 2

Sample Output 1

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

Sample Input 2

4
4 3 2 1

Sample Output 2

6

Source: PC Koshien 2016 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2016-11-12
http://web-ext.u-aizu.ac.jp/pc-concours/