Minimum Operations to Sort Books

We are given \(n\) books labeled from \(1\) to \(n\). The books are arranged in an arbitrary order initially. In each operation, you can extract a contiguous segment of books and insert it into any other position (preserving the order of books in the segment). The objective is to obtain the sorted order of books \(1, 2, \ldots, n\).

It can be shown that the minimum number of operations required is \(n - L\), where \(L\) is the length of the longest chain of consecutive books (by their labels) that appear in order in the current arrangement. Formally, if we denote \(pos[i]\) as the index of book \(i\) in the current arrangement (with indices starting at 0), then we want to find the maximum \(L\) such that for some \(i, i+1, \ldots, i+L-1\), we have \[ pos[i+1] > pos[i],\] for every consecutive pair in that chain. The answer is then given by:

[ \text{answer} = n - L. ]

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of books. The second line contains \(n\) distinct integers \(a_1, a_2, \ldots, a_n\) which represent the current order of the books. Each \(a_i\) is a permutation of \(1, 2, \ldots, n\).

outputFormat

Output a single integer, which is the minimum number of operations required to sort the books in increasing order.

sample

4
2 3 1 4

1