KNJIGE  KNJIGE
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:
20190330 13:07:00
simple AC in one go


ankkt16:
20190207 19:13:50
its simple..thimk and implement type:) 

sajalagrawal14:
20190122 05:32:22
awesome logic . great question


pranjal_rai:
20170929 07:58:10
Last edit: 20170929 07:58:31 

nadstratosfer:
20170903 20:34:37
Good problem. Solution takes seconds to implement but finding the logic has bothered me for a while. 

aditya730:
20170205 18:27:35
GONESORT is a similar problem. 

tni_mdixit:
20160811 17:13:27
some more test cases please


minhthai:
20160224 10:33:47
such a nice problem! simple but not simple :D 

:.Mohib.::
20160125 08:59:40
Nice logic...!! 

Bhuvnesh Jain:
20151221 19:54:57
nice question!

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