Minimum Operations to Sort Books

You are given a stack of n books, each with a certain height. The heights of the books are given in an array and the order represents the current arrangement of the stack from top to bottom.

The goal is to determine the minimum number of operations required to arrange the books in non-decreasing order (i.e. for all i, \(a_i \le a_{i+1}\)). An operation can reverse a single continuous segment of books.

For example, if the books are arranged as [3, 2, 1, 4, 5], one operation (reversing the segment [3, 2, 1]) can sort the sequence to [1, 2, 3, 4, 5]. However, some sequences might need two operations.

Your task is to compute the minimum number of such operations needed to sort the books.

inputFormat

The input is given via standard input and consists of two lines. The first line contains a single integer (n) (the number of books). The second line contains (n) space-separated integers representing the heights of the books.

outputFormat

Output a single integer representing the minimum number of operations required to sort the books in non-decreasing order.## sample

4
1 2 3 4

0