Minimum Subarray Sort Operations

Given an array of $n$ integers, you are allowed to perform a subarray-sort operation. In one operation, you can choose any contiguous subarray $[l, r]$ (where $1 \le l \le r \le n$) and sort it in non-decreasing order. The goal is to make the entire array sorted in non-decreasing order using the minimum number of such operations.

More formally, let $a = [a_1, a_2, \ldots, a_n]$ be the given array. An operation consists of selecting indices $l$ and $r$ ($1 \le l \le r \le n$) and replacing the subarray $[a_l, a_{l+1}, \ldots, a_r]$ with its sorted version (in non-decreasing order). Determine the minimum number of operations required to sort the entire array $a$.

Note: If the array is already sorted, no operations are needed.

inputFormat

The input is given via standard input. The first line contains an integer $n$, the number of elements in the array. The second line contains $n$ space-separated integers representing the array.

outputFormat

Output via standard output the minimum number of subarray sort operations needed to make the entire array sorted in non-decreasing order.## sample

5
1 2 3 4 5

0