Find Rotation Count in a Rotated Sorted Array

Given a circularly sorted array of unique integers, determine the number of rotations performed on the original sorted array. The rotation count is equal to the index of the minimum element in the array.

For example, if the array is [4, 5, 1, 2, 3], the smallest element 1 is at index 2, so the rotation count is 2.

A rotated sorted array is generated by taking a sorted array \(S = [s_0, s_1, \ldots, s_{n-1}]\) and rotating it \(k\) times so that it becomes \( [s_k, s_{k+1}, \ldots, s_{n-1}, s_0, s_1, \ldots, s_{k-1}]\).

inputFormat

The first line contains an integer (n), the number of elements in the array. The second line contains (n) space-separated integers representing the rotated sorted array.

outputFormat

Output a single integer representing the rotation count (i.e., the index of the minimum element) in the array.## sample

5
1 2 3 4 5

0