A rotary lock's dial codes were originally stored in strictly increasing order (all distinct), then the whole sequence was rotated left by some unknown amount, so the list now reads as a suffix of the sorted order followed by its prefix. For example a sorted list 1 3 5 6 7 9 12 rotated left by 4 becomes 7 9 12 1 3 5 6.
Given the rotated list and a target code x, print the 0-indexed position of x within the rotated list, or -1 if x is not present. Solve it in logarithmic time.
Input format
Line 1: an integer n, the number of codes.
Line 2: n space-separated distinct integers: the rotated list.
Line 3: an integer x, the target code.
Output format
A single integer: the 0-indexed position of x in the rotated list, or -1.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each code, x <= 1000000000
- The codes are distinct; the list is a rotation of a strictly increasing sequence.