Finding the Pivot in a Rotated Sorted Array

You are given a rotated sorted array of integers. A rotated sorted array is originally sorted in ascending order and then rotated at some pivot. Your task is to determine the index of the smallest element (the pivot) in the array.

The problem can be described mathematically as follows. Given an array \(A\) of length \(n\), find the index \(i\) such that: \[ A[i] \leq A[(i-1+n) \mod n] \]

This index represents the pivot point where the rotation occurred. You are expected to solve this problem in \(O(\log n)\) time using a binary search approach.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains an integer \(n\) representing 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 to standard output (stdout) -- the index of the smallest element (pivot) in the array.

5
4 5 1 2 3

2