Determine how many cyclic shifts are needed to make an array sorted in nondecreasing order, or report that it is impossible.
You are given an array of integers. In one operation, you may rotate the entire array to the left by one position: the first element moves to the end, and every other element shifts one place to the left.
Your task is to find the minimum number of such operations needed to make the array sorted in nondecreasing order. If no sequence of rotations can make the array sorted, output -1.
A rotation by k positions means performing the one-step left rotation exactly k times.
After rotation, the array must be sorted in nondecreasing order from left to right. Equal values are allowed.
n.n integers a[1], a[2], ..., a[n].-1.1 <= n <= 1001 <= a[i] <= 100na[1..n], the array valuesPrint the minimum number of left cyclic shifts needed to sort the array, or -1 if impossible.
1 <= n <= 1001 <= a[i] <= 100Example 1
Input
4 3 4 1 2
Output
2
Explanation
Two left rotations transform the array into [1, 2, 3, 4], which is sorted.
Example 2
Input
3 1 3 2
Output
-1
Explanation
No cyclic rotation of the array becomes nondecreasing.
Example 3
Input
5 1 2 3 4 5
Output
0
Explanation
The array is already sorted, so no rotation is needed.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.