Problem

3 /3


Tri du panier

Problem

U  Akaki est un jeu de n cartes. Chaque carte contient exactement un entier compris entre 1 et 100 000. Il est possible que les mêmes numéros soient écrits sur certaines cartes.
Akaki a décidé de trier toutes les cartes du jeu. Pour ce faire, il prend à tour de rôle une carte du dessus de la pioche et si le nombre inscrit dessus est égal au minimum parmi tous les nombres restants de la pioche, il met cette carte de côté. Sinon, Akaki place cette carte au-dessous de la pioche et pioche la carte suivante du dessus de la pioche. Le processus se termine lorsqu'il ne reste plus de cartes dans le jeu. Nous pouvons supposer qu'Akaki connaît à tout moment le nombre minimum écrit sur certaines des cartes restantes dans le jeu, mais ne sait pas où cette carte (ou ces cartes) se trouve dans le jeu.
Votre tâche consiste à déterminer le nombre total de fois qu'Akaki regarde la carte du dessus du paquet.
 
Entrée
La première ligne est suivie d'un entier positif n (1 ≤ n ≤ 100 000) — le nombre de cartes dans le jeu.
La deuxième ligne contient une suite de n entiers positifs a1, a2, ..., an ( 1 ≤ ai ≤ 100 000), où ai est égal au nombre inscrit sur la ième carte du dessus à partir de le pont.< /div>
 
Sortie
 
Imprimez le nombre total de fois qu'Akaki regarde la carte du dessus du jeu.

Entrez
Sortie
4
6 3 1 2
7
1
1000
1
7
3 3 3 3 3 3 3
7


Remarque
Dans le premier exemple, Akaki va d'abord regarder la carte avec le chiffre 6, la mettre en bas du paquet, puis la carte avec le chiffre 3, la mettre également en bas du paquet, puis la carte avec le numéro 1. Il mettra de côté la carte avec le numéro 1, puisqu'elle contient le nombre minimum restant dans le jeu. Après cela, les cartes du paquet se trouveront dans l'ordre [2, 6, 3] de haut en bas. Après cela, Akaki regardera la carte du dessus avec le numéro 2 et la mettra de côté. Après cela, les cartes du paquet seront dans l'ordre [6, 3] de haut en bas. Ensuite, Akaki regardera la carte avec le numéro 6, la mettra au fond du paquet, puis la carte avec le numéro 3, qu'il mettra de côté. Après cela, une carte portant le numéro 6 restera dans le jeu, qu'Akaki examinera et mettra de côté. Ainsi, Akaki regardera 7 cartes.
 
(c) Kurbatov E., 2018

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!