Search in Rotated Sorted Array

You are given a rotated sorted array of n unique integers and an integer target. The array is initially sorted in ascending order but then rotated at some unknown pivot. Your task is to search for the target in the rotated array and return its index if it is found; otherwise, return -1.

You should implement an algorithm with a runtime complexity of O(log n). The answer must be produced by reading input from standard input (stdin) and writing output to standard output (stdout).

Note: The array is zero-indexed.

Example 1:
Input: 7, [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Example 2:
Input: 7, [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -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.

The third line contains an integer representing the target value.

outputFormat

Output a single integer which is the index of the target in the array if it is found; otherwise, output -1.

## sample

7
4 5 6 7 0 1 2
0

4

</p>