Search in Rotated Sorted Array

Mediumjavapythonccppjavascript

A sorted array of distinct values has been rotated at an unknown pivot. Find the index of a given target using an efficient search.

Input Format

The first line contains two integers N and target. The second line contains N space-separated distinct integers — a sorted array that has been rotated.

Output Format

Print the index of target, or -1 if it is absent.

Example 1

Input

7 0
4 5 6 7 0 1 2

Output

Explanation: The target 0 is at index 4.

Input (stdin)

Output

Run your code to see output here...