Module: cartesian tree


Problem

3 /3


Cart Sorting

Problem

U  Akaki is a deck of n cards. Each card has exactly one integer from 1 to 100 000 written on it. It is possible that the same numbers are written on some cards.
Akaki decided to sort all the cards in the deck. To do this, he takes in turn one top card from the deck and if the number written on it is equal to the minimum among all the remaining numbers in the deck, he puts this card aside. Otherwise, Akaki puts this card on the bottom of the deck and draws the next card from the top of the deck. The process ends when there are no cards left in the deck. We can assume that Akaki at any time knows the minimum number written on some of the remaining cards in the deck, but does not know where this card (or cards) is located in the deck.
Your task is to determine the total number of times that Akaki looks at the top card from the deck.
 
Input
The first line is followed by a positive integer n (1 ≤ n ≤ 100 000) — the number of cards in the deck.
The second line contains a sequence of n positive integers a1, a2, ..., an ( 1 ≤ ai ≤ 100 000), where ai is equal to the number written on the i-th top card from the deck.< /div>
 
Output
 
Print the total number of times Akaki looks at the top card of the deck.

Enter Output
4
6 3 1 2
7
1
1000 		1
7
3 3 3 3 3 3 3 		7


Note
In the first example, Akaki will first look at the card with the number 6, put it at the bottom of the deck, then the card with the number 3, also put it at the bottom of the deck, and then the card with the number 1. He will put the card with the number 1 aside, since it contains the minimum number from remaining in the deck. After that, the cards in the deck will lie in the order [2, 6, 3] from top to bottom. After that, Akaki will look at the top card with the number 2 and put it aside. After that, the cards in the deck will lie in the order [6, 3] from top to bottom. Then Akaki will look at the card with the number 6, put it on the bottom of the deck, and then the card with the number 3, which he will set aside. After that, one card with the number 6 will remain in the deck, which Akaki will look at and set aside. Thus, Akaki will look at 7 cards.
 
(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!