KNJIGE - KNJIGE

no tags 

 

Mirko has a home library consisting of N books arranged one on top of the other in a narrow cabinet.
Since being well trained in the secrets of alphabet in the previous task, he now wishes to arrange the
books alphabetically, so that the book whose title comes first alphabetically ends up on top, and the
alphabetically last one at the bottom of the pile.
Mirko can easily pull a book out of the cabinet, but it is difficult to push it back into the pile, so the
book can only be returned to the top of the pile. Thus, the only available method of sorting the books
is repeatedly pulling a book out of the pile and placing it on top of the pile.
The books are labelled with integers from 1 to N, in alphabetical order. Therefore, Mirko wants them
to be ordered as (1, 2, ..., N), counting from the top. For example, if N = 3 and the starting order is (3,
2, 1), two moves are sufficient. First, he pulls out the book number 2 and places it on top, so the pile
becomes (2, 3, 1). After that, he does the same with book number 1, thus the pile becomes (1, 2, 3).
Help Mirko by calculating the minimum number of moves needed to sort a given starting order.
INPUT
The first line of input contains the integer N (N ≤ 300 000).
Each of the next N lines contains a single positive integer. These N integers represent the order of
Mirko’s books from top to bottom of the cabinet. Each of the integers 1, 2, ..., N appears exactly once.
OUTPUT
The first and only line of output must contain the required minimum number of moves.

 

Mirko has a home library consisting of N books arranged one on top of the other in a narrow cabinet. Since being well trained in the secrets of alphabet in the previous task, he now wishes to arrange the books alphabetically, so that the book whose title comes first alphabetically ends up on top, and the alphabetically last one at the bottom of the pile.

Mirko can easily pull a book out of the cabinet, but it is difficult to push it back into the pile, so the book can only be returned to the top of the pile. Thus, the only available method of sorting the books

is repeatedly pulling a book out of the pile and placing it on top of the pile.

The books are labelled with integers from 1 to N, in alphabetical order. Therefore, Mirko wants them to be ordered as (1, 2, ..., N), counting from the top.

For example, if N = 3 and the starting order is (3, 2, 1), two moves are sufficient. First, he pulls out the book number 2 and places it on top, so the pile becomes (2, 3, 1). After that, he does the same with book number 1, thus the pile becomes (1, 2, 3).

Help Mirko by calculating the minimum number of moves needed to sort a given starting order.

 

Input

The first line of input contains the integer N (N ≤ 300 000).

Each of the next N lines contains a single positive integer. These N integers represent the order of

Mirko’s books from top to bottom of the cabinet. Each of the integers 1, 2, ..., N appears exactly once.

Output

The first and only line of output must contain the required minimum number of moves.

Example

Input:
3 
3 
2 
1 

Output:
2

hide comments
manyu2: 2019-03-30 13:07:00

simple AC in one go

ankkt16: 2019-02-07 19:13:50

its simple..thimk and implement type:)

sajalagrawal14: 2019-01-22 05:32:22

awesome logic . great question
implementation is simple!!!!!

Last edit: 2019-01-22 05:34:16
pranjal_rai: 2017-09-29 07:58:10

Last edit: 2017-09-29 07:58:31
nadstratosfer: 2017-09-03 20:34:37

Good problem. Solution takes seconds to implement but finding the logic has bothered me for a while.

aditya730: 2017-02-05 18:27:35

GONESORT is a similar problem.

tni_mdixit: 2016-08-11 17:13:27

some more test cases please

minhthai: 2016-02-24 10:33:47

such a nice problem! simple but not simple :D

:.Mohib.:: 2016-01-25 08:59:40

Nice logic...!!

Bhuvnesh Jain: 2015-12-21 19:54:57

nice question!


Added by:Omar ElAzazy
Date:2012-02-13
Time limit:0.358s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64