Search in Rotated Sorted Array

You are given a sorted array that has been rotated at an unknown pivot. Formally, the array is initially sorted in ascending order and then rotated at some pivot \(k\), such that the array becomes \(A = [a_k, a_{k+1}, \ldots, a_{n-1}, a_0, a_1, \ldots, a_{k-1}]\). Your task is to search for a given integer \(target\) in this array. If the target exists, output its index; otherwise, output \(-1\).

The array contains distinct integers and is guaranteed to have been rotated an arbitrary number of times (possibly 0). You are expected to solve this problem with an algorithm that has a logarithmic runtime complexity \(O(\log n)\), typically using a modified binary search.

inputFormat

The input is read from stdin and consists of three parts:

• The first line contains an integer \(n\) denoting the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the rotated sorted array.
• The third line contains an integer \(target\), the value to search for.

outputFormat

Output a single integer to stdout representing the index of \(target\) in the array if found, otherwise output \(-1\).

## sample

7
4 5 6 7 0 1 2
0

4

</p>