Minimum Prefix Reversal Operations to Sort Books

You are given a stack of N books arranged in a row, each book marked with a unique number. Your task is to sort the books in increasing order (from left to right) using only a prefix reversal operation. A prefix reversal operation selects the first k books (for some 1 ≤ k ≤ N) and reverses their order.

It turns out that the minimum number of such operations required can be computed as N minus the length of the longest contiguous increasing subsequence in the current arrangement.

For example, consider the list [4, 3, 2, 1, 5]: the longest contiguous increasing subsequence is [1, 5] with a length of 2, so the minimum number of operations required is 5 − 2 = 3.

Your task is to implement a program that, given the number of books and their current ordering, computes this minimum number of prefix reversal operations.

inputFormat

The input is read from standard input and consists of two lines:

• The first line contains a single integer N (1 ≤ N ≤ 10⁵), representing the number of books.
• The second line contains N space-separated integers, representing the current ordering of the books.

outputFormat

Output a single integer to standard output: the minimum number of prefix reversal operations needed to sort the books in increasing order.

5
4 3 2 1 5

3