Find the Unsorted Subarray

Given an array of integers, your task is to find the length of the shortest contiguous subarray which, if sorted, would result in the entire array being sorted in non-decreasing order.

This problem can be formulated as follows. Consider an array \(A\) of \(n\) integers. Determine the smallest subarray \(A[i...j]\) such that when this subarray is sorted, the entire array \(A\) becomes sorted. If the array is already sorted, then the answer is 0.

Input Example: For the array [2, 6, 4, 8, 10, 9, 15], sorting the subarray [6, 4, 8, 10, 9] will result in a fully sorted array.

Note: It is guaranteed that \(1 \leq n \leq 10^5\) and each element of \(A\) is within the range of a 32-bit signed integer.

inputFormat

The first line 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 denoting the length of the shortest subarray that must be sorted in order for the whole array to be sorted in non-decreasing order.

7
2 6 4 8 10 9 15

5