Acakia hat ein Deck, das aus n Karten besteht. Auf jeder Karte steht genau eine ganze Zahl zwischen 1 und 100 000. Es ist möglich, dass auf einigen Karten die gleichen Zahlen geschrieben sind.
Acaky beschloss, alle Karten im Deck zu sortieren. Dazu nimmt er abwechselnd eine oberste Karte aus dem Deck und wenn die darauf geschriebene Zahl der minimalen unter allen verbleibenden Zahlen im Deck entspricht, legt er diese Karte beiseite. Andernfalls legt Akaki diese Karte auf das Deck und nimmt die nächste Karte von oben auf das Deck. Der Prozess endet, wenn keine Karten mehr im Deck verbleiben. Man kann davon ausgehen, dass Acaky zu jedem Zeitpunkt die Mindestzahl kennt, die auf einer der verbleibenden Karten im Deck notiert ist, aber nicht weiß, wo sich diese Karte (oder Karten) im Deck befindet.
Sie haben die Aufgabe, die Gesamtzahl der Male zu bestimmen, die die oberste Karte aus dem Deck sehen wird.
Eingabe
In der ersten Zeile folgt eine positive ganze Zahl n (1 ≤ n ≤ 100 000) — die Anzahl der Karten im Deck.
In der zweiten Zeile folgt eine Folge von n positiven ganzen Zahlen a1, a2, ..., an (1 ≤ ai ≤ 100 000), wobei ai gleich der Zahl ist, die oben auf der Karte des Decks auf der i geschrieben ist.
Ausgabe
Entferne die Gesamtzahl der Male, die Akaky die oberste Karte aus dem Deck sehen wird.
|
Eingabe |
Ausgabe |
|
4
6 3 1 2
|
7 |
1
1000 |
1 |
7
3 3 3 3 3 3 3 |
7 |
Hinweis
Im ersten Beispiel wird Akaki zuerst die Karte mit der Nummer 6 betrachten, sie auf das Deck legen, dann die Karte mit der Nummer 3, sie auch auf das Deck legen und dann die Karte mit der Nummer 1. Er wird die Karte mit der Nummer 1 beiseite legen, da die minimale Anzahl der verbleibenden im Deck darauf geschrieben ist. Danach werden die Karten im Deck in der Reihenfolge [2, 6, 3] von oben nach unten liegen. Danach wird Akaky die oberste Karte mit der Nummer 2 betrachten und sie beiseite legen. Danach werden die Karten im Deck in der Reihenfolge [6, 3] von oben nach unten liegen. Dann wird Acaky die Karte mit der Nummer 6 betrachten, sie auf das Deck legen und dann die Karte mit der Nummer 3 beiseite legen. Danach wird eine Karte mit der Nummer 6 im Deck verbleiben, die Acakis betrachten und beiseite legen wird. So wird Acaky 7 Karten sehen.
(c) Kurbatov E., 2018