円形の駐車タワーがある。$N$ 個の区画が円形に並び、時計回りに 1 番、2 番、……、$N$ 番の区画と呼ぶ。各区画には車が 1 台あり、$i$ 番の区画の車の番号は $a_i$ である。

タワーには 2 つのボタンがある。ボタン A を押すと時計回りに、ボタン B を押すと反時計回りに、1 区画分回転できる。下の左図は上の例で A を押した後、右図は B を押した後の状態を表す。

このタワーからすべての車を取り出したい。

車を取り出せるのは一番下の 1 区画だけである。初期状態では 1 番の区画が一番下にある。他の区画の車を取り出すには、まず適切にボタンを押してタワーを回転させ、その区画を一番下へ移す必要がある。

さらに、番号 $x$ の車を取り出す前に、番号が $x$ より小さい車をすべて取り出さなければならない。つまり、番号が $x$ 未満の車が残っていれば、番号 $x$ の車は取り出せない。

すべての車を取り出すために必要なボタンを押す合計回数の最小値を求めるプログラムを作成せよ。

制約

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

小課題

1. (8 点) $a_i=1$（$1\le i\le N$）、つまりすべての車の番号が 1 である。
2. (9 点) $i\ne j$ なら $a_i\ne a_j$。つまりすべての車の番号が異なる。
3. (10 点) $N\le10$。
4. (21 点) $N\le100$。
5. (31 点) $N\le1\,000$。
6. (21 点) 追加の制約はない。

入力

1 行目に整数 $N$ が与えられる。

2 行目に車の番号 $a_1,\ldots,a_N$ が順に空白区切りで与えられる。

出力

1 行目に、必要なボタンを押す合計回数の最小値を出力せよ。

入出力例

入力 1

4
1 2 2 1

出力 1

3

注記

車を取り出す → ボタン A → 車を取り出す → ボタン A → 車を取り出す → ボタン A → 車を取り出す、の順に操作すればよい。

入力 2

5
3 1 4 5 1

出力 2

7