Head over meals
All submissions for this problem are available.
Adam, an Adasaurus, works for a dish washing company. He comes across a pile consisting of N plates with a number tag each placed one on top of the other. He wishes to arrange the plates in the increasing order of the tag number. Though a plate can be pulled out of the stand, but it can only be returned to the top of the pile. Therefore, he can only sort the plates by repeatedly pulling out a plate and placing it on the top of the pile.
The plates are labelled with numbers from 1 to N. So, they need to be ordered as (1, 2, ..., N), counting from the top. For example, if N = 3 and the starting order is (1, 3, 2), two moves are sufficient. First, pulling out the plate number 2 and placing it on top makes the order (2, 1, 3) and similarly with plate number 1 makes the final order (1, 2, 3).
You need to help Adam sort the given starting order in minimum number of moves.
The first input line contains the integer N (N <= 300 000) and the subsequent N lines contain a single positive integer representing the order of Adam's plates from top to bottom of the pile. Also note that these integers 1, 2, 3,..., N appear exactly once.
Print the minimum number of moves required on a single line.
Input: 3 1 3 2 Output: 2
|Time Limit:||0.312343 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions