Search in Rotated Sorted Array

You are given a rotated sorted array and a target value. Your task is to write a program that finds the index of the given target in the array using an efficient search algorithm. If the target is not present in the array, your program should output -1.

A rotated sorted array is a sorted array that has been rotated at some pivot unknown to you beforehand. For example, the array [4, 5, 6, 7, 0, 1, 2] is a rotated version of the sorted array [0, 1, 2, 4, 5, 6, 7].

Your solution must read input from standard input and write the result to standard output.

Note: The array is zero-indexed.

inputFormat

The input is given from standard input and consists of three lines:

1. The first line contains an integer n which is the number of elements in the array.
2. The second line contains n space-separated integers representing the rotated sorted array.
3. The third line contains a single integer representing the target value to search for.

For example:

7 4 5 6 7 0 1 2 0

outputFormat

Output a single integer on standard output, which is the index of the target element in the array. If the target is not found, output -1.## sample

7
4 5 6 7 0 1 2
0

4