Minimum Operations to Sort Books

You are given a collection of books represented by distinct integers. Your task is to determine the minimum number of operations required to arrange the books in ascending order. In one operation, you can move a book such that its relative ordering changes. The optimal strategy involves identifying the longest increasing subsequence (LIS) in the provided sequence—these books are already in the correct relative order and do not need to be moved. The answer is given by the formula (n - \text{LIS}), where (n) is the total number of books.

This problem assesses your knowledge of greedy algorithms and dynamic programming (specifically using binary search to compute the LIS efficiently).

inputFormat

The first line contains an integer (n) (1 (\leq) n (\leq) 10⁵) which indicates the number of books. The second line contains (n) space-separated integers representing the current order of the books. It is guaranteed that all integers are distinct.

outputFormat

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

5
3 1 4 2 5

2