Search in Rotated Sorted Array

You are given a rotated sorted array and a target integer. In a rotated sorted array, the array is initially sorted in ascending order and then rotated at an unknown pivot. Your task is to determine the index of the target in the array. If the target does not exist, output -1.

Note that an efficient solution with a time complexity of $\mathcal{O}(\log n)$ is expected by performing a modified binary search.

inputFormat

The first line of input is an integer $n$, 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$, which is the value to search for.

outputFormat

Output a single integer representing the index of the target in the array or -1 if the target is not present.## sample

7
4 5 6 7 0 1 2
0

4