Minimum Subarray Length to Sort

Given an array of integers, determine the length of the smallest contiguous subarray that, when sorted, results in the entire array being in non-decreasing order.

If the array is already sorted, simply output 0.

For example, if the input array is [1, 3, 5, 4, 2, 6, 7], sorting the subarray [3, 5, 4, 2] (which has length 4) will make the whole array sorted.

The key idea is to find indices start and end such that sorting the subarray from index start to end (represented in LaTeX as $end - start + 1$) results in a sorted array.

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 representing the elements of the array.

outputFormat

Output a single integer, which is the length of the smallest contiguous subarray that needs to be sorted so that the entire array becomes sorted in non-decreasing order. If the array is already sorted, output 0.

5
1 2 3 4 5

0