Search in Rotated Sorted Array

Problem statement

A catalogue of distinct integers was sorted and then rotated. Find the position of a requested identifier in the current catalogue. Return -1 if it is missing. The catalogue may also be unrotated; use logarithmic search.

Input format

First line: n target. Second line: n catalogue values.

Output format

Print the zero-based index of target, or -1.

Constraints

1 <= n <= 100000; distinct values and target are between -1000000000 and 1000000000.

Sample input

5 2
7 9 1 2 4

Sample output

3