Minimum Operations to Sort Array via Rotation

You are given an array of n integers, denoted as \(a_1, a_2, \dots, a_n\). In one operation, you remove the first element of the array and append it to the end. Your task is to determine the minimum number of such operations required so that the array becomes sorted in non-decreasing order. If it is impossible to achieve this by performing the operation any number of times, output \(-1\).

More formally, let the array be \(a = [a_1, a_2, \dots, a_n]\). In one operation, transform \(a\) into \(a' = [a_2, a_3, \dots, a_n, a_1]\). Find the minimum number of operations \(k\) such that if we rotate the array \(k\) times, the resulting array \(a'\) is sorted in non-decreasing order. If no such \(k\) exists, output \(-1\).

For example, if \(a = [3, 4, 5, 1, 2]\), then after 3 operations the array becomes \([1, 2, 3, 4, 5]\), which is sorted. Hence, the answer is 3.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains a single integer \(n\) (the size of the array).
2. The second line contains \(n\) space-separated integers representing the array elements \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer to standard output (stdout): the minimum number of operations required to make the array sorted in non-decreasing order. If it is impossible, print \(-1\).

5
3 4 5 1 2

3