Minimum Operations to Sort Books

You are given a sequence of n books, where the height of the i-th book is given by an integer. The books must be arranged in non-decreasing order (i.e. sorted by height from smallest to largest). In one operation, you are allowed to use a special process that can correct almost the entire sequence except possibly one misplaced book.

If the sequence is already sorted, no operation is necessary. Otherwise, if a contiguous subarray (of size n - 1) is already sorted, you can fix the whole sequence in one operation. In other cases, you will need exactly two operations.

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

Note: All formulas are given in LaTeX format. For example, the condition that a subarray is sorted can be written as \(a_i \le a_{i+1}\) for all valid \(i\).

inputFormat

The input is read from standard input (stdin) and contains two lines:

• The first line contains an 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, which is the minimum number of operations required to sort the books in non-decreasing order, printed to standard output (stdout).

## sample

5
4 3 2 6 1

2

</p>