Search in a Rotated Sorted Array

Medium#searching #binary-search· solved by 0 · time limit 2.0 s

A sorted array of distinct values was rotated at an unknown point (e.g. 4 5 6 7 0 1 2). Find the index of $x$ or print -1 — in $O(\log n)$ .

Input

$n$ and the rotated array, then $x$ .

The index or -1.

$1 \le n \le 10^5$

Input

7
4 5 6 7 0 1 2
0

Output

Input

7
4 5 6 7 0 1 2
3

Output

-1