P6549 [COCI 2010/2011 #2] KNJIGE

Mirko has a home library consisting of $n$ books. The $n$ books are arranged one after another in a narrow cabinet. Since he practiced letters well in the previous task, he now wants to arrange the books in alphabetical order, so that the book whose title is the smallest in lexicographical order is at the top, and the book whose title is the largest in lexicographical order is at the bottom. Mirko can easily pull a book out of the cabinet, but it is hard to push it back in. Therefore, he can only put a book back onto the top of the cabinet. As a result, the only available way to sort the books is to repeatedly pull a book out of the cabinet and place it on the top. The books are labeled with integers from $1$ to $n$ in alphabetical order. Therefore, Mirko wants to sort them from top to bottom into $(1,2,\cdots,n)$. For example, if $n = 3$ and the initial order is $(3,2,1)$, then two moves are enough. First, he pulls out the book numbered $2$ and puts it on the top, so the order becomes $(2,3,1)$. After that, he does the same with the book numbered $1$, so the order becomes $(1,2,3)$. Given the initial order, compute the minimum number of moves needed to finish sorting.

The first line contains an integer $n$, as described in the statement. The next $n$ lines each contain one positive integer, describing the initial order of the books.

Output one integer on a single line, representing the minimum number of moves required to arrange the books in increasing order.

#### Constraints For $100\%$ of the data, it is guaranteed that $1 \leq n \leq 3 \times 10^5$, and the initial order of the books is a permutation of $1 \ldots n$. #### Notes - This problem is worth $80$ points. - Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) KNJIGE. Translator: @[mnesia](https://www.luogu.com.cn/user/115711)。 Translated by ChatGPT 5