Module: albero cartesiano


Problem

3 /3


Ordinamento del carrello

Problem

U  Akaki è un mazzo di n carte. Su ogni carta è scritto esattamente un numero intero compreso tra 1 e 100 000. È possibile che su alcune carte siano scritti gli stessi numeri.
Akaki ha deciso di ordinare tutte le carte nel mazzo. Per fare ciò, prende a sua volta una carta in cima al mazzo e se il numero scritto su di essa è uguale al minimo tra tutti i numeri rimanenti nel mazzo, mette da parte questa carta. Altrimenti, Akaki mette questa carta in fondo al mazzo e pesca la carta successiva dalla cima del mazzo. Il processo termina quando non ci sono più carte nel mazzo. Possiamo presumere che Akaki in qualsiasi momento conosca il numero minimo scritto su alcune delle carte rimanenti nel mazzo, ma non sappia dove si trova questa carta (o carte) nel mazzo.
Il tuo compito è determinare il numero totale di volte in cui Akaki guarda la prima carta del mazzo.
 
Input
La prima riga è seguita da un numero intero positivo n (1 ≤ n ≤ 100 000) — il numero di carte nel mazzo.
La seconda riga contiene una sequenza di n numeri interi positivi a1, a2, ..., an ( 1 ≤ ai ≤ 100 000), dove ai è uguale al numero scritto sulla i-esima prima carta da il mazzo.< /div>
 
Uscita
 
Stampa il numero totale di volte in cui Akaki guarda la prima carta del mazzo.

Entra Uscita
4
6 3 1 2
7
1
1000 		1
7
3 3 3 3 3 3 3 		7


Nota
Nel primo esempio, Akaki guarderà prima la carta con il numero 6, la metterà in fondo al mazzo, poi la carta con il numero 3, anch'essa la metterà in fondo al mazzo, e poi la carta con il numero 1. Mette da parte la carta con il numero 1, poiché contiene il numero minimo da rimanere nel mazzo. Dopodiché, le carte nel mazzo saranno nell'ordine [2, 6, 3] dall'alto verso il basso. Dopodiché, Akaki guarderà la prima carta con il numero 2 e la metterà da parte. Dopodiché, le carte nel mazzo saranno nell'ordine [6, 3] dall'alto verso il basso. Quindi Akaki guarderà la carta con il numero 6, la metterà in fondo al mazzo, e poi la carta con il numero 3, che metterà da parte. Dopodiché, nel mazzo rimarrà una carta con il numero 6, che Akaki guarderà e metterà da parte. Quindi, Akaki guarderà 7 carte.
 
(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!