Determine how many cyclic shifts are needed to make an array sorted in nondecreasing order, or report that it is impossible.
Problem
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.
Clarification
After rotation, the array must be sorted in nondecreasing order from left to right. Equal values are allowed.
Input Format
- The first line contains an integer
n. - The second line contains
nintegersa[1], a[2], ..., a[n].
Output Format
- Print the minimum number of left rotations needed to make the array sorted in nondecreasing order.
- If it is impossible, print
-1.
Constraints
1 <= n <= 1001 <= a[i] <= 100
Hints
- A rotated sorted array can have at most one position where the order decreases.
- Try each possible rotation only if needed; the array is small enough for straightforward checking.
Input Format
na[1..n], the array values
Output Format
Print the minimum number of left cyclic shifts needed to sort the array, or -1 if impossible.
Constraints
1 <= n <= 1001 <= a[i] <= 100
Example 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.
Show 1 more example
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
Unlock deeper context for this problem
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.