U アカキは n 枚のカードのデッキです。各カードには、1 から 100 000 までの整数が 1 つだけ書かれています。一部のカードに同じ数字が書かれている可能性があります。
赤木は山札のカードをすべて並べ替えることにした。これを行うために、彼は順番に山札から一番上のカードを 1 枚取り、そこに書かれている数字が山札の残りのすべての数字の最小値に等しい場合、彼はこのカードを脇に置きます。そうでない場合、アカキはこのカードを山札の一番下に置き、山札の上から次のカードを引く。デッキにカードが残っていない場合、プロセスは終了します。 Akaki は、デッキの残りのカードのいくつかに書かれている最小数をいつでも知っていると想定できますが、このカード (または複数のカード) がデッキのどこにあるかはわかりません.
あなたの仕事は、アカキが山札の一番上のカードを見た合計回数を決定することです。
入力
最初の行の後には、正の整数 n (1 ≤ n ≤ 100 000) — が続きます。デッキ内のカードの数。
2 行目には、n 個の正の整数 a
1, a
2, ..., a
n ( 1 ≤ a
i ≤ 100 000)、ここで a
i は i 番目の一番上のカードに書かれている数字に等しいデッキ。< /div>
出力
赤木が山札の一番上のカードを見た合計回数を出力せよ。
<本体>
|
入る |
出力 |
|
4
6 3 1 2
|
7 |
1
1000
|
1 |
7
3 3 3 3 3 3 3
|
7 |
注意
最初の例では、アカキは最初に数字の 6 のカードを見て、それを山札の一番下に置き、次に数字の 3 のカードを見て、それも山札の一番下に置き、次に番号 1. 彼は番号 1 のカードを脇に置きます。これは、デッキに残っている最小の番号が含まれているためです。その後、デッキ内のカードは上から[2、 6、 3]の順番で配置されます。その後、アカキは一番上の2のカードを見て脇に置きます。その後、山札のカードは上から[6, 3]の順番で並びます。次に、赤木は番号6のカードを見て、それを山札の一番下に置き、次に番号3のカードを脇に置きます.その後、デッキに6番のカードが1枚残り、アカキはそれを見て脇に置きます.したがって、アカキは 7 枚のカードを見ることになります。
(c) Kurbatov E.、2018年