404. Search in Rotated Sorted Array

0

Medium

Given an array that is initially sorted in ascending order and then rotated at an unknown pivot point, you need to find the index of a target value in the array. If the target value is found, return its index; otherwise, return -1. It is guaranteed that there are no duplicate elements in the array.

Input Format

The first line of input contains the size of the array. The second line contains the elements of the array. The third line contains the target value.

Output Format

Print the index of the target element if found; otherwise, print -1.

Example

Input

7
4 5 6 7 0 1 2
0

Output

4

Constraints

The algorithm must have a runtime complexity of O(log n).

Loading...

View Submissions

Console