Sorting Books
|
All submissions for this problem are available.
Indraneel has to sort the books in his library. His library has one long shelf. His books are numbered $1$ through $N$ and he wants to rearrange the books so that they appear in the sequence $1,2, ..., N$. He intends to do this by a sequence of moves. In each move he can pick up any book from the shelf and insert it at a different place in the shelf. Suppose Indraneel has $5$ books and they are initially arranged in the order $$2 \quad 1 \quad 4 \quad 5 \quad 3$$ Indraneel will rearrange this in ascending order by first moving book $1$ to the beginning of the shelf to get $$1 \quad 2 \quad 4 \quad 5 \quad 3$$ Then, moving book $3$ to position $3$, he gets $$1 \quad 2 \quad 3 \quad 4 \quad 5$$ Your task is to write a program to help Indraneel determine the minimum number of moves that are necessary to sort his book shelf. ###Input: The first line of the input will contain a single integer $N$ indicating the number of books in Indraneel's library. This is followed by a line containing a permutation of $1, 2, ..., N$ indicating the intial state of Indraneel's book-shelf. ###Output: A single integer indicating the minimum number of moves necessary to sort Indraneel's book-shelf. ###Constraints: - $1 \leq N \leq 200000$. - You may also assume that in $50 \%$ of the inputs, $1 \leq N \leq 5000$. ###Sample Input 5 2 1 4 5 3 ###Sample Output 2| Author: | admin2 |
| Date Added: | 17-09-2018 |
| Time Limit: | 2 sec |
| Source Limit: | 50000 Bytes |
| Languages: | C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS |
Comments
- Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
