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.
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.
The first and only line of output must contain the required minimum number of moves.
Input: 3 3 2 1 Output: 2
Really a nice question
it took me time! If you are about to use logic related to the next greater number problem, I'm warning you there's more to it. But it can be done, enjoy. !(simple && AC in one go)
simple AC in one go
its simple..thimk and implement type:)
awesome logic . great question
Last edit: 2017-09-29 07:58:31
Good problem. Solution takes seconds to implement but finding the logic has bothered me for a while.
GONESORT is a similar problem.
some more test cases please
such a nice problem! simple but not simple :D