Module: árvore cartesiana


Problem

3 /3


Classificação do Carrinho

Problem

U  Akaki é um baralho de n cartas. Cada cartão tem exatamente um número inteiro de 1 a 100 000 escrito nele. É possível que os mesmos números estejam escritos em alguns cartões.
Akaki decidiu separar todas as cartas do baralho. Para fazer isso, ele pega uma carta do topo do baralho e, se o número escrito nela for igual ao mínimo entre todos os números restantes do baralho, ele coloca essa carta de lado. Caso contrário, Akaki coloca esta carta no fundo do baralho e compra a próxima carta do topo do baralho. O processo termina quando não houver mais cartas no baralho. Podemos assumir que Akaki a qualquer momento sabe o número mínimo escrito em algumas das cartas restantes do baralho, mas não sabe onde esta carta (ou cartas) está localizada no baralho.
Sua tarefa é determinar o número total de vezes que Akaki olha para a carta do topo do baralho.
 
Entrada
A primeira linha é seguida por um inteiro positivo n (1 ≤ n ≤ 100 000) — o número de cartas no baralho.
A segunda linha contém uma sequência de n inteiros positivos a1, a2, ..., an ( 1 ≤ ai ≤ 100 000), onde ai é igual ao número escrito na i-ésima carta superior de o baralho.< /div>
 
Saída
 
Imprima o número total de vezes que Akaki olha para a carta do topo do baralho.

Entrar Saída
4
6 3 1 2
7
1
1000 		1
7
3 3 3 3 3 3 3 		7


Nota
No primeiro exemplo, o Akaki vai primeiro olhar a carta com o número 6, colocar no fundo do baralho, depois a carta com o número 3, colocar também no fundo do baralho e depois a carta com o número 1. Ele deixará a carta com o número 1 de lado, pois contém o número mínimo para sobrar no baralho. Depois disso, as cartas do baralho ficarão na ordem [2, 6, 3] de cima para baixo. Depois disso, Akaki vai olhar para a carta do topo com o número 2 e colocá-la de lado. Depois disso, as cartas do baralho ficarão na ordem [6, 3] de cima para baixo. Em seguida, Akaki vai olhar a carta com o número 6, colocá-la no fundo do baralho e, a seguir, a carta com o número 3, que ele colocará de lado. Depois disso, uma carta com o número 6 ficará no baralho, que Akaki examinará e colocará de lado. Assim, Akaki olhará para 7 cartas.
 
(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!