A sorted array of distinct integers was rotated at an unknown pivot (e.g. 4 5 6 7 0 1 2). Find the index of the target in O(log n).

Input: line 1 — the rotated array; line 2 — the target. Output: the 0-based index, or -1.

Your program reads from stdin and prints to stdout.