Minimum Operations to Make Array Non-decreasing

You are given an array of n integers. In each operation, you can pick any contiguous subarray and multiply every element in that subarray by -1.

Your task is to determine the minimum number of operations required to transform the given array into a non-decreasing array. An array is non-decreasing if it satisfies $$a_i \le a_{i+1}$$ for all valid indices i.

Example:
For the array [3, -1, 4, 2, -5], one optimal sequence of operations can make the array non-decreasing in 2 operations.

inputFormat

The first line of input contains a single integer n (the number of elements in the array). The second line contains n space-separated integers describing the array.

outputFormat

Output a single integer representing the minimum number of operations required to make the array non-decreasing.

5
3 -1 4 2 -5

2