Smallest Subarray to Reverse

You are given an array of n integers. Your task is to determine the minimum length of a contiguous subarray which, if reversed, will result in the entire array being sorted in non-decreasing order.

If the array is already sorted, then the answer is \(0\).

Note: A subarray is a contiguous portion of the array. Reversing a subarray means that the order of the elements in that subarray is reversed.

Example:

• For the array [1, 3, 5, 4, 2], reversing the subarray [3, 5, 4, 2] yields [1, 2, 4, 5, 3] which is not sorted; however, reversing the subarray [3, 5, 4, 2] in the correct segment (from index 1 to 4) transforms the array into [1, 2, 4, 5, 3]. The intended correct reversal needs to be determined by comparing with the fully sorted array.
• The proper approach is to compare the given array to its sorted version and determine the leftmost and rightmost indices where they differ. The length of the subarray between these indices (inclusive) is the minimum length required.

Formally, let the array be \(a_1, a_2, \dots, a_n\) and its sorted version be \(s_1, s_2, \dots, s_n\). Find the smallest indices \(i\) and \(j\) (with \(1 \leq i \leq j \leq n\)) such that \(a_i \neq s_i\) and \(a_j \neq s_j\). The answer is \(j - i + 1\). If no such indices exist, output \(0\).

inputFormat

The input is given via standard input:

• The first line contains an integer \(n\) (\(1 \leq n \leq 10^5\)) indicating the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements. Each integer is within the range of a typical 32-bit signed integer.

outputFormat

Output a single integer to standard output — the length of the smallest contiguous subarray that needs to be reversed to make the entire array sorted in non-decreasing order. If the array is already sorted, output \(0\).

## sample

3
1 2 3

0